Most Frequent Substring

You are given a string S and an integer K. Your task is to find the most frequent substring of length K in S. In the event that multiple substrings have the same maximum frequency, you should output the lexicographically smallest one.

For example, given S = "ababc" and K = 2, the substring "ab" appears most frequently. Similarly, if S = "aabbaabb" and K = 3, then "aab" is the desired answer. The solution should efficiently process multiple test cases.

Input Constraints: It is guaranteed that K is a valid length for a substring of S.

The intended algorithm involves counting the occurrences of each substring of length K and determining which one has the highest frequency, with ties broken lexicographically (i.e., using the standard dictionary order).

All formulas, if any, must be in \(\LaTeX\) format. (No formulas are required for this problem.)

inputFormat

The first line of input contains an integer \(T\), representing the number of test cases. Each test case consists of a single line containing an integer \(K\) and a string \(S\), separated by a space.

For example:

3
2 ababc
3 aabbaabb
1 zzzz

outputFormat

For each test case, output the most frequent substring of length \(K\) in \(S\) on a separate line. If there are multiple substrings with the same frequency, output the lexicographically smallest one.

## sample

3
2 ababc
3 aabbaabb
1 zzzz

ab
aab
z

</p>