T = int(input())

for t in range(1, T+1):
    A, B, Q = input().split()
    A = A.strip()
    B = B.strip()
    Q = int(Q)

    # precompute longest common prefixes for all possible suffixes of B
    lcp = [0] * len(B)
    for i in range(len(B)-1):
        j = lcp[i]
        while j > 0 and B[i+1] != B[j]:
            j = lcp[j-1]
        if B[i+1] == B[j]:
            lcp[i+1] = j+1

    # perform sequence analysis tests
    results = []
    for q in range(Q):
        P, S = map(int, input().split())
        aprefix = A[:P]
        bsuffix = B[-S:]
        matchlen = 0
        for i in range(len(bsuffix)):
            j = matchlen
            while j > 0 and bsuffix[i] != aprefix[j]:
                j = lcp[j-1]
            if bsuffix[i] == aprefix[j]:
                j += 1
            matchlen = max(matchlen, j)
        results.append(matchlen)

    # output results
    print("Case #{}: {}".format(t, " ".join(str(x) for x in results)))