# function to perform sequence analysis test
def perform_test(A, B, P, S):
    max_len = 0
    for i in range(P):
        if A[i:P] in B[-S:]:
            max_len = max(max_len, P-i)
    return max_len

# main function
def main():
    t = int(input())
    for case in range(1, t+1):
        A, B, q = input().split()
        q = int(q)
        ans = []
        for i in range(q):
            P, S = map(int, input().split())
            ans.append(perform_test(A, B, P, S))
        print("Case #{}: {}".format(case, " ".join(str(x) for x in ans)))

if __name__ == '__main__':
    main()