Given a string S and integer N, your task is to compute the substring of length N that is repeated most in the string.

If two substrings of length N have the same occurrence count in S, return the smallest lexicographically.

Input

The first line contains the number of test cases T. T <= 10.

The following T lines hold the test cases, each line consisting of integer N followed by string S. N and S are space separated. N <= 100, |S| <= 100000 .

Output

Print T lines, each containing the substring of length N that is most frequent. If two substrings have the same occurrence count, print the smallest lexicographically.

Example

Input:
2
2 efababefef
1 aabebb

Output:
ef
b