While shopping, Morgan noticed that a supermarket has a big sale.

He bought some products from that supermarket and found them defective. Each product has an alphanumeric code (all codes have equal lengths). He noticed that all the defective products begins with the same characters, but there were too many of them to be checked.

As you are his friend, he gave you the codes of the defective products and asked you to find the longest common beginning of them.

Input

The first line of input begins with a line containing T the number of test cases.

Each testcase starts with a line contains a number (0 < n ≤ 1000) indicating the number of defective products Morgan bought,

followed by n lines each contains an alphanumeric strings s_i (|s_i| ≤ 100) the code of the i-th defective product, all n strings have the same length.

Output

For each test case print a line containing a string the longest common beginning of the codes of defective products.

Example

Input:
1
3
a1BdcX
a1Brm8
a1B3Sy

Output:
a1B