There is a string a (unknown to you), consisting of lowercase Latin letters, encrypted according to the following rule into string s after each character of string a

, an arbitrary (possibly zero) number of any lowercase Latin letters, different from the character itself, is added;

after each such addition, the character that we supplemented is added.

You are given string s

, and you need to output the initial string a

. In other words, you need to decrypt string s

Note that each string encrypted in this way is decrypted uniquely.

Input

The first line of the input contains a single integer t

?(1≤t≤1000) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single integer n

?(2≤n≤100) — the length of the encrypted message.

The second line of each test case contains a string s of length n

?— the encrypted message obtained from some string a

Output

For each test case, output the decrypted message a

?on a separate line.

Example

3

8

abacabac

5

qzxcq

20

ccooddeeffoorrcceess

outputCopy

ac

q

codeforces

Note

In the first encrypted message, the letter a

?is encrypted as aba

, and the letter c

?is encrypted as cabac

.In the second encrypted message, only one letter q

?is encrypted as qzxcq

In the third encrypted message, zero characters are added to each letter.

就是當出現(xiàn)一個字符的時候，記錄下來，然后中間是無關的信息，當再次出現(xiàn)相同的字符的時候，就意味著下一個字符可以添加進來了。依次求出字符串代表的信息；

用變量可以做，用棧也可以的。

我是用的棧；下面是代碼：