def solution():
    a,b,n = input().split()
    n = int(n)
    
    arr = [list(map(int,input().split())) for _ in range(n)]
    
    ans = []
    
    for i in arr:
        m = 0
        a1 = a[:i[0]]
        b1 = b[len(b)-i[1]:]
        
        while(len(a1)>0):
            t1 = a1[:]
            while(len(t1) > 0):
                if t1 == b1[:len(t1)]:
                    if len(t1)>m:
                        m = len(t1)
                
                t1 = t1[:-1]
            a1 = a1[1:]
        
        ans.append(m)
    
    print(*ans)
            



t = int(input())
for _ in range(t):
    solution()