J :: SH4R3C0D3

Time Limit: 10 Seconds    Memory Limit: 65536 KB

In a galaxy far far away, a war is happening between planet SH4R3 and planet C0D3. The military forces of SH4R3 need your help to hack into C0D3's mother-ship communication system and inject some data that turns off all of the N battleships that C0D3 military force controls. Each battleship has a 7-character long code, with distinct characters, that turns off the engine if seen in a received message from the mother-ship. For example if the code is "destroy" for a battleship, it'll turn off the engine once it receives a message that contains that string, like "abcdestroydefg".

We have all the turn off codes for all the battleships, and we've already hacked into C0D3's mother-ship broadcast system. We just need to construct the string payload and broadcast to all the battleships. Since sending a character through our hacked link is expensive, we want to minimize the length of the payload.

The security system of the battleship B_i, prevents the engine to turn off unless B_i-1 is already turned off. So we need a strategic plan to turn off the battleships in order from 1 to N.

But that's not the only security system the battleships have in place. The firmware on the C0D3's battleships has a basic algorithm that detects if a message is a spam and should be thrown away, or if it's a legitimate message and should be executed. The algorithm is simple, a legitimate message is always a palindrome.

Now it's your job to find the shortest palindrome message that turns off all the battleships in order.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 128), which is the number of test cases.

Each test begins with an integer N, the number of battleships. The next line contains N 7-character long turnoff commands, for battleship 1 through N.

Output

For each test case, print the payload that we need to broadcast through mother-ship disable battleships and win the war.

If multiple possible solution exists, print the one that is lexicographically smaller.

Each answer is guaranteed to be less than 100 characters long.

Sample Input

2
2
destroy destroy
3
shareck areckod okcerah

Sample Output

destroyortsedestroyortsed
shareckodokcerahs

Submit

Source: 15th Iran Nationwide Internet Contest