A. Shortest Substring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a string $$$s$$$, let $$$f(s)$$$ be the string obtained by merging possibly several consecutive equal characters into a single character. For example, $$$f(abbbccdc) = abcdc$$$.

Given a string $$$a$$$, find the shortest substring $$$b$$$ of $$$a$$$ such that $$$f(a)$$$ is equal to $$$f(b)$$$.

Input

The first line will have $$$t$$$, the number of test cases – ($$$1 \le t \le 50$$$).

The first line of each test case will have $$$n$$$, the length of string $$$a$$$ – ($$$1 \le n \le 100$$$).

The second line of each test case will have string $$$a$$$ of length $$$n$$$ which contains only lower case characters from $$$a$$$ to $$$z$$$.

Output

For each test case, output a single line with string $$$b$$$.

Example
Input
2
8
abbbccdc
3
zzz
Output
abbbccdc
z