def sequence_analysis(A, B, Q):
    """
    This function takes two strings A and B and an integer Q as input and returns the length of the longest substring from the A-prefix that matches the B-suffix for each of the Q sequence analysis tests.

    Parameters:
    A (str): The first sequence.
    B (str): The second sequence.
    Q (int): The number of sequence analysis tests.

    Returns:
    list: A list of the length of the longest substring from the A-prefix that matches the B-suffix for each of the Q sequence analysis tests.
    """
    # Initialize the list to store the results
    results = []

    # Iterate through each of the Q sequence analysis tests
    for i in range(Q):
        # Get the prefix size for the A sequence
        p = int(input())
        # Get the suffix size for the B sequence
        s = int(input())
        # Get the A-prefix
        a_prefix = A[:p]
        # Get the B-suffix
        b_suffix = B[-s:]
        # Initialize the longest substring length
        longest_substring_length = 0
        # Iterate through each substring of the A-prefix
        for j in range(len(a_prefix)):
            # Get the substring
            substring = a_prefix[j:]
            # Check if the substring is a prefix of the B-suffix
            if substring == b_suffix[:len(substring)]:
                # Update the longest substring length
                longest_substring_length = max(longest_substring_length, len(substring))
        # Append the longest substring length to the results
        results.append(longest_substring_length)

    return results


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

# Iterate through each test case
for t in range(T):
    # Get the two strings and the number of sequence analysis tests
    A, B, Q = input().split()
    Q = int(Q)
    # Get the results
    results = sequence_analysis(A, B, Q)
    # Print the results
    print("Case #{}: {}".format(t+1, " ".join(map(str, results))))