378QAQ has a string $$$s$$$ of length $$$n$$$. Define the core of a string as the substring$$$^\dagger$$$ with maximum lexicographic$$$^\ddagger$$$ order.
For example, the core of "$$$\mathtt{bazoka}$$$" is "$$$\mathtt{zoka}$$$", and the core of "$$$\mathtt{aaa}$$$" is "$$$\mathtt{aaa}$$$".
378QAQ wants to rearrange the string $$$s$$$ so that the core is lexicographically minimum. Find the lexicographically minimum possible core over all rearrangements of $$$s$$$.
$$$^\dagger$$$ A substring of string $$$s$$$ is a continuous segment of letters from $$$s$$$. For example, "$$$\mathtt{defor}$$$", "$$$\mathtt{code}$$$" and "$$$\mathtt{o}$$$" are all substrings of "$$$\mathtt{codeforces}$$$" while "$$$\mathtt{codes}$$$" and "$$$\mathtt{aaa}$$$" are not.
$$$^\ddagger$$$ A string $$$p$$$ is lexicographically smaller than a string $$$q$$$ if and only if one of the following holds:
For example, "$$$\mathtt{code}$$$" and "$$$\mathtt{coda}$$$" are both lexicographically smaller than "$$$\mathtt{codeforces}$$$" while "$$$\mathtt{codeforceston}$$$" and "$$$\mathtt{z}$$$" are not.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 10^5$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 10^6$$$) — the length of string $$$s$$$.
The next line of each test case contains the string $$$s$$$ of length $$$n$$$. The string $$$s$$$ consists of lowercase English letters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output the lexicographically minimum possible core over all rearrangements of $$$s$$$.
63qaq4cccc6bazoka6zazzzz7ababbbb7ccbabcc
qaq cccc z zzz bbababb cbcacbc
In the first test case, all possible rearrangements and their corresponding cores are as follows:
So the core with the minimum lexicographic order in all rearrangement plans is "$$$\mathtt{qaq}$$$".
Name |
---|