def longest_common_prefix(s1, s2):
    """
    Returns the length of the longest common prefix of s1 and s2.
    """
    n = min(len(s1), len(s2))
    for i in range(n):
        if s1[i] != s2[i]:
            return i
    return n

def solve_test_case(A, B, Q, queries):
    """
    Solves a single test case and returns a list of answers for the queries.
    """
    n = len(A)
    m = len(B)
    LCP_A = [0] * n
    LCP_B = [0] * m
    for i in range(1, n):
        LCP_A[i] = longest_common_prefix(A[i:], A)
    for i in range(m - 1):
        LCP_B[m - i - 1] = longest_common_prefix(B[m - i - 1:], B)
    answers = []
    for P, S in queries:
        answer = longest_common_prefix(A[:P], B[m - S:])
        answers.append(answer)
    return answers

# Read input
T = int(input())
for t in range(1, T + 1):
    A, B, Q = input().split()
    A = A.strip()
    B = B.strip()
    Q = int(Q)
    queries = []
    for i in range(Q):
        P, S = map(int, input().split())
        queries.append((P, S))
    # Solve test case
    answers = solve_test_case(A, B, Q, queries)
    # Print output
    print("Case #{}: {}".format(t, " ".join(str(x) for x in answers)))