I. Linguistics Puzzle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

When preparing for the International Collegiate Linguistics Contest, Mr. Ham meets an unknown language X. He is given an integer $$$n$$$ ($$$2\leq n\leq 52$$$) and $$$n^2$$$ numbers written in Language X. The $$$n^2$$$ numbers are generated by the following rules:

  • Generate a sequence $$$a_0,a_1,\ldots,a_{n^2-1}$$$ that satisfies $$$a_{n\cdot i+j}=i\cdot j$$$ for all $$$0\le i,j<n$$$.
  • Shuffle the sequence.

Mr. Ham is an experienced ICLCer. He finds out some basic rules of Language X:

  • There are $$$n$$$ different symbols in Language X. Mr. Ham uses the first $$$n$$$ lowercase letters to represent them if $$$n\le 26$$$. Otherwise, he uses the first $$$26$$$ lowercase letters and the first $$$n-26$$$ uppercase letters to represent them.
  • The numbers in Language X are written in base $$$n$$$. Each digit is represented by a symbol in Language X.
  • Like in Arabic numerals, the digits are written from the most significant digit to the least significant digit, i.e. $$$\mathtt{a}\cdot n+\mathtt{b}$$$ is written as $$$\mathtt{ab}$$$ instead of $$$\mathtt{ba}$$$. There are no leading zeros, i.e. $$$\mathtt{a}$$$ is written as $$$\mathtt{a}$$$ instead of $$$\mathtt{0a}$$$.

Mr. Ham wants to know which symbol represents digit $$$i$$$ in Language X for each $$$0\le i<n$$$. He asks you for help.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le 50$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 52$$$), the number of symbols in Language X.

The second line contains $$$n^2$$$ strings $$$s_1,s_2,\dots,s_{n^2}$$$, the numbers in Language X. Each string consists of at most $$$2$$$ lowercase and uppercase letters.

It is guaranteed that the answer exists.

Output

Output a string of length $$$n$$$, the $$$i$$$-th character is the symbol that represents digit $$$i-1$$$ in Language X.

If there are multiple answers, output any of them.

Examples
Input
2
3
a b a b b b b c cc
4
d d d d d c b a d b cd cb d a cb bc
Output
bca
dcba
Input
2
4
d a a bc ba bc b a a a d a a cb c c
4
a b da b b d ad b db b a c da b c b
Output
abcd
bdac
Note

In the first test case of the first sample, the letter $$$\mathtt{b}$$$ represents digit $$$0$$$, the letter $$$\mathtt{c}$$$ represents digit $$$1$$$, and the letter $$$\mathtt{a}$$$ represents digit $$$2$$$. The numbers given in the input are $$$1,0,1,0,0,0,0,2,4$$$.