import sys

def rolling_hash(s, p):
    # Rabin-Karp rolling hash function
    base = 26
    mod = 10**9 + 7
    h = 0
    for i in range(p):
        h = (h * base + ord(s[i]) - ord('A')) % mod
    return h

def solve_case(case_num, A, B, Q, queries):
    # precompute hash values for all substrings of A and B
    max_p = max(P for P, _ in queries)
    max_s = max(S for _, S in queries)
    A_hashes = [rolling_hash(A[i:i+p], p) for p in range(1, max_p+1) for i in range(len(A)-p+1)]
    B_hashes = [rolling_hash(B[i:i+s], s) for s in range(1, max_s+1) for i in range(len(B)-s+1)]
    # build hash table for A
    A_hash_table = {}
    for i, h in enumerate(A_hashes):
        A_hash_table.setdefault(h, []).append(i)
    # look up hash values for B-suffixes and compare to A-prefix
    result = []
    for i, (P, S) in enumerate(queries):
        prefix_hash = rolling_hash(A[:P], P)
        suffix_hashes = set(rolling_hash(B[i:i+S], S) for i in range(len(B)-S+1))
        max_len = 0
        for h in suffix_hashes:
            if h in A_hash_table:
                for j in A_hash_table[h]:
                    if A[j:j+P] == B[i:i+P]:
                        max_len = max(max_len, P)
                        break
        result.append(max_len)
    # output results
    print("Case #{}: {}".format(case_num, " ".join(str(x) for x in result)))

# read input
T = int(input())
for i in range(T):
    A, B, Q = input().split()
    Q = int(Q)
    queries = []
    for j in range(Q):
        P, S = map(int, input().split())
        queries.append((P, S))
    solve_case(i+1, A, B, Q, queries)