Most Frequent Subpattern

Problem Description:

Given a sequence of symbols represented as a string (s) of length (n) and an integer (k), determine the sub-pattern (substring) of length (k) that appears most frequently in (s). In case there are multiple sub-patterns with the same maximum frequency, return the lexicographically smallest one.

Formally, consider all substrings of length (k) from (s) (there are (n-k+1) such substrings). Let the frequency of a substring be the number of times it occurs in (s). Your task is to output the substring with the highest frequency. If there is a tie, output the smallest one in lexicographical order.

Note: A sub-pattern is defined as any contiguous substring of the given string.

inputFormat

Input is read from standard input (stdin) and begins with a single integer (T) representing the number of test cases. Each test case consists of three lines:
1. An integer (n), the length of the string.
2. A string (s) consisting of symbols.
3. An integer (k), the length of the sub-pattern.

outputFormat

For each test case, print the most frequent sub-pattern of length (k) on a new line. If multiple substrings have the maximum frequency, output the lexicographically smallest one.## sample

3
6
abcabc
2
5
aaaaa
2
7
abcdefg
3

ab
aa
abc