# Function to find the length of the longest common prefix between two strings
def longest_common_prefix(s1, s2):
    n = min(len(s1), len(s2))
    for i in range(n):
        if s1[i] != s2[i]:
            return i
    return n

# Function to find the length of the longest common suffix between two strings
def longest_common_suffix(s1, s2):
    n = min(len(s1), len(s2))
    for i in range(1, n+1):
        if s1[-i] != s2[-i]:
            return i-1
    return n

# Function to find the length of the longest substring from the A-prefix that matches the B-suffix
def find_longest_match(A, B, P, S):
    a_prefix = A[:P]
    b_suffix = B[-S:]
    return longest_common_prefix(a_prefix, b_suffix)

# Function to run a batch of sequence analysis tests
def batch_sequence_tests(A, B, tests):
    results = []
    for P, S in tests:
        match_len = find_longest_match(A, B, P, S)
        results.append(match_len)
    return results

# Read the number of test cases
T = int(input())

# Iterate over the test cases
for t in range(1, T+1):
    # Read the input for this test case
    A, B, Q = input().split()
    Q = int(Q)
    tests = []
    for i in range(Q):
        P, S = map(int, input().split())
        tests.append((P, S))

    # Run the sequence analysis tests and print the results
    results = batch_sequence_tests(A, B, tests)
    result_str = ' '.join(str(r) for r in results)
    print("Case #{}: {}".format(t, result_str))