def longest_prefix_suffix(A, B, P, S):
    res = []
    for i in range(len(P)):
        j = S[i] - 1
        while j >= 0 and A[P[i] + j - S[i] + 1] == B[j]:
            j -= 1
        res.append(S[i] - j - 1)
    return res

T = int(input())
for t in range(T):
    A, B, Q = input().split()
    A = list(A)
    B = list(B)
    Q = int(Q)
    P = []
    S = []
    for i in range(Q):
        p, s = input().split()
        P.append(int(p))
        S.append(int(s))
    ans = longest_prefix_suffix(A, B, P, S)
    print("Case #{}: {}".format(t+1, " ".join(str(x) for x in ans)))