def longest_substring(A, B):
    n = len(A)
    m = len(B)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
    return dp

T = int(input()) # number of test cases
for t in range(1, T + 1):
    A, B, Q = input().split() # read input for each test case
    Q = int(Q)
    prefix_lengths = []
    suffix_lengths = []
    for i in range(Q):
        Pi, Si = map(int, input().split()) # read prefix and suffix lengths
        prefix_lengths.append(Pi)
        suffix_lengths.append(Si)
    
    # calculate longest substring for each test case
    dp = longest_substring(A, B)
    result = []
    for i in range(Q):
        Pi = prefix_lengths[i]
        Si = suffix_lengths[i]
        longest_match = 0
        for j in range(1, Si + 1):
            longest_match = max(longest_match, dp[Pi][m - j + 1])
        result.append(longest_match)
    
    # print results
    print("Case #{}: {}".format(t, " ".join(map(str, result))))