T = int(input())

for case in range(1, T+1):
    A, B, Q = input().split()
    A, B, Q = str(A), str(B), int(Q)
    M = len(A)
    N = len(B)
    result = []
    
    # Preprocess the suffixes of B
    suffix_matches = [0] * N
    for j in range(N):
        for k in range(j, N):
            if B[j:k+1] in A:
                suffix_matches[j] = k-j+1
                
    # Process each query
    for i in range(Q):
        P, S = input().split()
        P, S = int(P), int(S)
        longest_match = 0
        for j in range(M-P+1):
            if B[-S:][:min(S, suffix_matches[j+P-1])] in A[j:j+P]:
                longest_match = max(longest_match, min(S, suffix_matches[j+P-1]))
        result.append(longest_match)
        
    print("Case #{}: {}".format(case, ' '.join(map(str, result))))