Palindrome

Interview

Time limit1sMemory limit256 MB

Summary

From the given words, pick two at different positions so their concatenation is a palindrome and report the lexicographically smallest one.

Level: Easy3 of 10
Topics: Brute force, String, Two pointers
Solved: No attempts yet

Problem

A palindrome is a word that reads the same forwards and backwards. For example, civic, radar, rotor, and madam are palindromes.

A notebook contains $k$ words made of lowercase letters. You want to pick two words at different positions and concatenate them in order so that the result is a palindrome. That is, for two distinct indices $i \ne j$ , check whether the string formed by appending the $j$ -th word right after the $i$ -th word is a palindrome. (The same word cannot be used twice.)

For example, when the words are aaba, ba, ababa, bbaa, and baaba, appending ba after ababa forms the palindrome abababa.

Given $k$ words, write a program that finds such a palindrome.

Input

The first line contains the number of test cases $T$ . For each test case, the first line contains the number of words $k$ ( $1 \le k \le 100$ ) written in the notebook. Each of the next $k$ lines contains one word made of lowercase letters from a to z. Within a single test case, the sum of the lengths of all words is at most 10,000.

Output

For each test case, print a palindrome that can be formed, one per line. If several palindromes are possible, print the lexicographically smallest one. If no palindrome can be formed, print 0.

Examples5

Example 1

Input

2
5
aaba
ba
ababa
bbaa
baaba
3
abc
bcd
cde

Expected output

abababa
0

Example 2
Input
```
1
1
abc
```
Expected output
```
0
```
Example 3
Input
```
1
2
aa
aa
```
Expected output
```
aaaa
```
Example 4
Input
```
1
2
ab
cd
```
Expected output
```
0
```
Example 5
Input
```
1
3
ab
ba
a
```
Expected output
```
aba
```