def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        (g, y, x) = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    (g, x, y) = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def shash(s):
    m = 18446744073709551557
    p = 31
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    alpha = {alphabet[i] : i+1 for i in range(len(alphabet))}

    hashes = [alpha[i] for i in s]

    pi = modinv(p,m)
    pp = 1

    pinv = [1 for i in s]

    for i in range(1,len(s)):
        pp *= p
        pp %= m

        hashes[i] *= pp
        hashes[i] += hashes[i-1]
        hashes[i] %= m

        pinv[i] = (pinv[i-1] * pi) % m
    
    return (hashes, pinv)

def subhash(hashes,pinv,start,stop):
    m = 18446744073709551557
    H = hashes[stop-1]
    if start > 0:
        H -= hashes[start-1]
    H %= m
    H *= pinv[start]
    H %= m
    return H

def solve():
    global m,p
    [s1,s2,Q] = input().split()
    Q = int(Q)

    (hashes_s1,pinv_s1) = shash(s1)
    (hashes_s2,pinv_s2) = shash(s2)

    ans = []
    for i in range(Q):
        [pi,si] = [int(j) for j in input().split()]

        s2_start = len(s2) - si

        flag=False

        left = 0
        right = min(pi, si)

        while left + 3 <= right:
            ss_len = (left+right) // 2

            possible = False

            SH = subhash(hashes_s2, pinv_s2, s2_start, s2_start + ss_len)

            for start in range(pi-ss_len+1):
                if subhash(hashes_s1, pinv_s1, start, start+ss_len) == SH:
                    possible = True
                    break
            
            if possible:
                left = ss_len
            else:
                right = ss_len-1
        
        (left,right) = (min(left,right), max(left,right))
        while left <= min(right+3,min(pi, si)):
            if left == 0:
                left += 1
            else:
                ss_len = left

                possible = False

                SH = subhash(hashes_s2, pinv_s2, s2_start, s2_start + ss_len)

                for start in range(pi-ss_len+1):
                    if subhash(hashes_s1, pinv_s1, start, start+ss_len) == SH:
                        possible = True
                        break
                
                if not possible:
                    break
                else:
                    left+=1
        left-=1
        
        ans.append(left)
    
    return " ".join(list(map(str,ans)))

for T in range(1,int(input())+1):
    print("Case #{}: {}".format(T,solve()))