Card String

Interview

Time limit1sMemory limit256 MB

Summary

Given uppercase letters taken left to right, each new card is placed at the front or back of the growing string; find the lexicographically smallest result.

Level: Medium4 of 10
Topics: Greedy, String, Implementation, Brute force
Solved: No attempts yet

Problem

$N$ cards lie in a row. Each card has one uppercase letter written on it. Taeuk may take the cards one at a time, always the leftmost card still in the row. The first card he takes goes in front of him as it is. Every later card he places at the far left or at the far right of the cards already in front of him. After he has taken every card, reading the letters in front of him from left to right gives a card string.

Suppose three cards lie in the order M, K, U. Taeuk first takes the card with M and puts it in front of him. If he then takes the card with K and puts it at the far left, and takes the card with U and again puts it at the far left, he gets UKM. If he puts the card with K at the far left and the card with U at the far right, he gets KMU. Among the strings he can build this way, KMU comes first in lexicographic order.

Given the initial order of the letters on the cards, print the card string that comes first in lexicographic order among the ones Taeuk can build.

Input

Input comes from standard input. The first line has the number of test cases $T$ ( $1 \le T \le 100$ ). The first line of each test case has the number of cards $N$ ( $1 \le N \le 1000$ ) that lie in the row at the start. The second line has the $N$ letters on the cards, given in order from the leftmost card and separated by spaces. Every letter is uppercase, and each card carries exactly one letter.

Output

Write to standard output. For each test case, print on its own line the card string that comes first in lexicographic order among the ones Taeuk can build.

Examples5

Example 1

Input

3
3
M K U
5
A S D F G
7
B A C A B A C

Expected output

KMU
ASDFG
AAABCBC

Example 2
Input
```
1
1
Z
```
Expected output
```
Z
```

Example 3

Input

2
10
A A A A A A A A A A
1
Q

Expected output

AAAAAAAAAA
Q

Example 4

Input

2
8
A B C D E F G H
8
H G F E D C B A

Expected output

ABCDEFGH
ABCDEFGH

Example 5

Input

3
8
B A B A B A B A
8
A B A B A B A B
9
A A A B B B A A A

Expected output

AAAABBBB
AAAABBBB
AAAAAABBB