def preprocess(A, B):
    # Compute the longest common prefix of A and all possible suffixes of B
    L = [[0 for j in range(len(B))] for i in range(len(B))]
    for i in range(len(B)):
        for j in range(len(B)-i):
            if i == 0 or j+i >= len(B):
                L[i][j] = 0
            elif A[i-1] == B[j+i-1]:
                L[i][j] = L[i-1][j+1] + 1
            else:
                L[i][j] = 0
    return L

T = int(input())
for test_case in range(1, T+1):
    # Read input
    A, B, Q = input().split()
    Q = int(Q)
    P = [0] * Q
    S = [0] * Q
    for i in range(Q):
        P[i], S[i] = map(int, input().split())

    # Preprocess the sequences
    L = preprocess(A, B)

    # Answer each query
    ans = []
    for i in range(Q):
        # Find the maximum value of L[S[i]][j] for all matching prefixes of A and suffixes of B
        max_len = 0
        for j in range(len(B)-S[i]+1):
            if A[:P[i]] == B[j:j+P[i]]:
                max_len = max(max_len, L[S[i]][j])
        ans.append(max_len)

    # Print output
    print("Case #{}: {}".format(test_case, " ".join(map(str, ans))))