t = int(input())

for tc in range(t):
    t-=1
    a, b, q = input().split()
    answers = []
    for qc in range(int(q)):
        pi, si = map(int, input().split())
        ap = a[:pi]
        bs = b[-si:]
        
        for i in range(min(len(ap), len(bs)),-1,-1):
            if ap.find(bs[:i])!=-1:
                answers.append(i)
                break        
    print('Case #'+str(tc+1)+':', end=' ')
    for ans in answers:
        print(ans, end=' ')
    print()