def solve_test_case(A, B, Q, tests):
    # Create a list to hold the results for each test in this case
    results = []
    # For each test, take the prefix and suffix sizes and compare
    for i in range(Q):
        P, S = tests[i]
        # Get the A-prefix and B-suffix
        a_prefix = A[:P]
        b_suffix = B[-S:]
        # Check for matches
        match_len = 0
        for j in range(min(P, S)):
            if a_prefix[j] != b_suffix[j]:
                break
            match_len += 1
        results.append(match_len)
    # Return the results for this case
    return results


# Main function to read input and solve test cases
if __name__ == '__main__':
    # Read the number of test cases
    T = int(input())
    # Process each test case
    for case_num in range(1, T+1):
        # Read the input for this case
        A, B, Q = input().split()
        Q = int(Q)
        tests = [list(map(int, input().split())) for i in range(Q)]
        # Solve the test case and print the results
        results = solve_test_case(A, B, Q, tests)
        print("Case #{}: {}".format(case_num, ' '.join(str(x) for x in results)))