t = int(input())

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

    ans = []
    for j in range(int(q)):
        max_len = 0
        for k in range(p[j]):
            for l in range(s[j]):
                if a[k] == b[-l-1]:
                    len = 1
                    while k+len < p[j] and l+len < s[j] and a[k+len] == b[-l-1-len]:
                        len += 1
                    if len > max_len:
                        max_len = len
        ans.append(max_len)

    print("Case #{}: {}".format(i, " ".join(str(x) for x in ans)))