def sequence_analysis_test(a, b, p, s):
    max_len = 0
    for i in range(p):
        if a[i:i+s] == b[:s]:
            max_len = s
            break
        for j in range(s-1, 0, -1):
            if a[i:i+j] == b[:j]:
                max_len = max(max_len, j)
                break
    return max_len


t = int(input())


for case in range(1, t+1):
   
    a, b, q = input().split()
    p = []
    s = []
    for i in range(int(q)):
        pi, si = map(int, input().split())
        p.append(pi)
        s.append(si)
    
    
    results = []
    for i in range(int(q)):
        result = sequence_analysis_test(a, b, p[i], s[i])
        results.append(result)