def solve_case(case_num, A, B, Q, queries):
    # calculate suffix array and LCP array for B
    n = len(B)
    sa = sorted(range(n), key=lambda i: B[i:])
    lcp = [0] * n
    for i in range(1, n):
        j = sa[i-1]
        k = sa[i]
        while k + lcp[i-1] < n and j + lcp[i-1] < n and B[j + lcp[i-1]] == B[k + lcp[i-1]]:
            lcp[i] += 1
    
    # answer each query
    ans = []
    for i in range(Q):
        P, S = queries[i]
        # find range of suffixes in B that start with A-prefix
        lo, hi = 0, n-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if B[sa[mid]:][:P] < A[:P]:
                lo = mid + 1
            else:
                hi = mid - 1
        if lo == n or B[sa[lo]:][:P] != A[:P]:
            ans.append(0)
            continue
        start = lo
        lo, hi = start, n-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if B[sa[mid]:][:P] == A[:P]:
                lo = mid + 1
            else:
                hi = mid - 1
        end = hi
        
        # find length of longest common prefix between A-prefix and matching B-suffixes
        max_len = 0
        for j in range(start, end+1):
            max_len = max(max_len, min(S, lcp[j]))
        ans.append(max_len)
    
    # output answers
    print("Case #{}: {}".format(case_num, " ".join(str(x) for x in ans)))

# read input and solve each test case
T = int(input())
for i in range(1, T+1):
    A, B, Q = input().split()
    Q = int(Q)
    queries = []
    for j in range(Q):