def find_longest_substring(prefix, suffix):
    longest_match = 0
    for i in range(len(prefix)):
        for j in range(len(suffix)):
            if prefix[i:] == suffix[j:j+len(prefix)-i]:
                longest_match = max(longest_match, len(prefix)-i)
    return longest_match

# Read input
T = int(input())
for case in range(1, T+1):
    A, B, Q = input().split()
    Q = int(Q)
    results = []
    for i in range(Q):
        P, S = map(int, input().split())
        prefix = A[:P]
        suffix = B[-S:]
        results.append(find_longest_substring(prefix, suffix))
    # Print output
    print(f"Case #{case}: {' '.join(map(str, results))}")