function hash_sequence(sequence):
    """This function returns a list of hash values of all prefixes of the given sequence."""
    hash_list = []
    hash_value = 0
    for i in range(len(sequence)):
        hash_value = (hash_value * PRIME + ord(sequence[i])) % MOD
        hash_list.append(hash_value)
    return hash_list

function solve_test_case(A, B, Q):
    """This function solves a single test case."""
    B_suffix_hash_table = {}
    for i in range(len(B)):
        suffix_hash = 0
        for j in range(i, min(i + MAX_S, len(B))):
            suffix_hash = (suffix_hash * PRIME + ord(B[j])) % MOD
            B_suffix_hash_table[suffix_hash] = j - i + 1

    A_prefix_hash = hash_sequence(A[:MAX_P])
    results = []
    for i in range(Q):
        P, S = read_input()
        max_match = 0
        for j in range(P):
            if j + S > len(B):
                break
            prefix_hash = (A_prefix_hash[j] * PRIME_P[S] + A_prefix_hash[j+S-1] - A_prefix_hash[j-1] * PRIME_P[S]) %