def substring_match(A, B, P, S):
    max_len = 0
    for i in range(P):
        for j in range(S):
            if A[i] == B[j]:
                k = 1
                while i + k < P and j + k < S and A[i+k] == B[j+k]:
                    k += 1
                if k > max_len:
                    max_len = k
    return max_len

t = int(input())
for case in range(1, t+1):
    A, B, q = input().split()
    P, S = map(int, input().split())
    print("Case #{}:".format(case), end=" ")
    for i in range(q):
        P_i, S_i = map(int, input().split())
        print(substring_match(A[:P_i], B[-S_i:], P_i, S_i), end=" ")
    print()