def longest_prefix_suffix(A, B, P, S):
    # Initialize the result list
    result = []
    # Iterate over the Q tests
    for i in range(len(P)):
        # Take the A-prefix of length P[i]
        prefix = A[:P[i]]
        # Take the B-suffix of length S[i]
        suffix = B[-S[i]:]
        # Initialize the length of the longest matching substring to 0
        max_len = 0
        # Iterate over all substrings of the A-prefix
        for j in range(len(prefix)):
            # Check if the substring matches the B-suffix
            if prefix[j:] == suffix[:len(prefix)-j]:
                # Update the length of the longest matching substring
                max_len = len(prefix)-j
        # Append the result of the test to the result list
        result.append(max_len)
    # Return the result list
    return result


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

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

    # Compute the result
    result = longest_prefix_suffix(A, B, P, S)

    # Print the output
    print("Case #{}: {}".format(t, " ".join(str(x) for x in result)))