def solve_test_case(a, b, q, queries):
    prefix_matches = {}  # stores the longest matching prefix for each suffix of b
    for i in range(len(b)):
        for j in range(i+1, len(b)+1):
            prefix = a[:j-i]
            suffix = b[i:j]
            if suffix.startswith(prefix):
                prefix_matches[j] = max(prefix_matches.get(j, 0), j-i)
    
    results = []
    for p, s in queries:
        results.append(prefix_matches.get(s, 0))
    
    return results

# main function
def main():
    t = int(input())
    for case in range(1, t+1):
        a, b, q = input().split()
        q = int(q)
        queries = [tuple(map(int, input().split())) for _ in range(q)]
        results = solve_test_case(a, b, q, queries)
        print("Case #{}: {}".format(case, " ".join(map(str, results))))