def compute_prefix_len(A, B):
    # Computes prefix_len table using dynamic programming
    n, m = len(A), len(B)
    prefix_len = [[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]:
                prefix_len[i][j] = prefix_len[i-1][j-1] + 1
            else:
                prefix_len[i][j] = 0
    return prefix_len

def solve_test_case(A, B, Q, queries):
    prefix_len = compute_prefix_len(A, B)
    res = []
    for i in range(Q):
        Pi, Si = queries[i]
        # look up the precomputed value in prefix_len
        max_len = prefix_len[Pi][Si]
        res.append(max_len)
    return res

T = int(input())
for t in range(1, T+1):
    A, B, Q = input().split()
    Q = int(Q)
    queries = []
    for i in range(Q):
        Pi, Si = map(int, input().split())
        queries.append((Pi, Si))
    ans = solve_test_case(A, B, Q, queries)
    ans_str = " ".join(str(x) for x in ans)
    print("Case #{}: {}".format(t, ans_str))