def genetic_sequences(T, test_cases):
    results = []
    for t in range(T):
        A, B, Q = test_cases[t][:3]
        queries = test_cases[t][3:]
        case_result = []
        for i in range(Q):
            P, S = queries[i]
            prefix = A[:P]
            suffix = B[-S:]
            longest_substring = 0
            for j in range(min(P, S)):
                if prefix[j] == suffix[j]:
                    longest_substring += 1
                else:
                    break
            case_result.append(longest_substring)
        results.append(case_result)
    return results

# Example usage
T = 3
test_cases = [("ABCABAC", "CABABA", 3, [(3, 6), (7, 6), (6, 5)]),
              ("BANANA", "HABANA", 2, [(5, 4), (5, 5)]),
              ("ABC", "ABD", 1, [(2, 1)])]
results = genetic_sequences(T, test_cases)
for i in range(T):
    print("Case #{}: {}".format(i+1, " ".join(map(str, results[i]))))