def solve_test_case(A, B, Q, queries):
    N = len(B)
    L = [[0] * (N+1) for _ in range(len(A)+1)]
    for i in range(1, len(A)+1):
        for j in range(1, N+1):
            if A[i-1] == B[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = 0

    ans = []
    for P, S in queries:
        max_len = 0
        for i in range(1, P+1):
            if N-S+i <= N:
                max_len = max(max_len, L[i][N-S+i])
        ans.append(max_len)
    return ans

T = int(input())
for t in range(1, T+1):
    A, B, Q = input().split()
    Q = int(Q)
    queries = []
    for i in range(Q):
        P, S = map(int, input().split())
        queries.append((P, S))
    ans = solve_test_case(A, B, Q, queries)
    print(f"Case #{t}: {' '.join(map(str, ans))}")