SKIPLIST - Yet another strings problem !!

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

Added by:ahmed.abdrabo
Date:2013-04-30
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UVA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.