# function to perform sequence analysis test
def sequence_analysis_test(A, B, P, S):
    max_match_lengths = []
    for i in range(len(P)):
        a_prefix = A[:P[i]]
        b_suffix = B[-S[i]:]
        max_match_length = 0
        for j in range(len(a_prefix)):
            if a_prefix[j:] not in b_suffix:
                break
            max_match_length = j + 1
        max_match_lengths.append(max_match_length)
    return max_match_lengths

# main function to read input and output results
def main():
    # read number of test cases
    T = int(input())

    # iterate over test cases
    for t in range(1, T+1):
        # read input
        A, B, Q = input().split()
        A = str(A)
        B = str(B)
        Q = int(Q)
        P = []
        S = []
        for i in range(Q):
            p, s = map(int, input().split())
            P.append(p)
            S.append(s)

        # perform sequence analysis test
        max_match_lengths = sequence_analysis_test(A, B, P, S)

        # output results
        print("Case #{}: {}".format(t, ' '.join(map(str, max_match_lengths))))

# run the program
if _name_ == "_main_":
    main()