# function to find the length of longest matching prefix-substring
def find_matching_length(a_prefix, b_suffix):
    n = min(len(a_prefix), len(b_suffix))
    for i in range(n):
        if a_prefix[i] != b_suffix[i]:
            return i
    return n

# main function
if __name__ == '__main__':
    t = int(input()) # number of test cases
    for case in range(1, t+1):
        # input for each test case
        a, b, q = input().split()
        q = int(q)
        # output format
        output = 'Case #' + str(case) + ':'
        # for each query
        for i in range(q):
            p, s = map(int, input().split())
            # find the prefix-substrings
            a_prefix = a[:p]
            b_suffix = b[-s:]
            # find the length of longest matching prefix-substring
            match_len = find_matching_length(a_prefix, b_suffix)
            # append to output
            output += ' ' + str(match_len)
        # print the output for the current test case
        print(output)