t = int(input())

for i in range(1, t+1):
    A, B, Q = input().split()
    Q = int(Q)
    
    print("Case #{}:".format(i), end=" ")
    
    for j in range(Q):
        P, S = map(int, input().split())
        A_prefix = A[:P]
        B_suffix = B[-S:]
        longest_prefix_suffix = 0
        
        for k in range(min(P, S), -1, -1):
            if A_prefix[-k:] == B_suffix[:k]:
                longest_prefix_suffix = k
                break
                
        print(longest_prefix_suffix, end=" ")
        
    print()