def longest_prefix_match(A, B, P, S):
    prefix_matches = [0] * P
    max_match = 0
    for i in range(P):
        for j in range(S):
            if A[i] == B[j]:
                if i == 0 or j == 0:
                    prefix_matches[i] = 1
                else:
                    prefix_matches[i] = prefix_matches[i-1] + 1
                max_match = max(max_match, prefix_matches[i])
            else:
                prefix_matches[i] = 0
    return max_match

# Main function to read input and output results
def sequence_analysis():
    T = int(input())
    for t in range(1, T+1):
        A, B, Q = input().split()
        Q = int(Q)
        results = []
        for q in range(Q):
            P, S = map(int, input().split())
            result = longest_prefix_match(A[:P], B[-S:], P, S)
            results.append(result)
        print("Case #{}: {}".format(t, " ".join(str(x) for x in results)))

# Example usage
sequence_analysis()