MRKT - Defective Products

no tags 

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 si (|si| ≤ 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

hide comments
ABHIJEET: 2015-12-27 20:48:49

should be moved to tutorial!!

=(Francky)=> Moved ; thanks.

Last edit: 2015-12-30 19:52:47
naruto09: 2015-12-27 06:52:33

please move to tutorial..-_-

Prakhar Dev Gupta: 2015-12-26 06:50:08

AC!
but has the question been removed from classical?? I didn't get the points

gomathi ganesan: 2015-12-25 07:17:49

Getting WA.
Are there any critical test cases?

Last edit: 2015-12-25 07:18:12
Tulika Vats: 2015-12-19 18:45:43

Properly compiling and giving correct answer on ideone. STILL WA!! Why??
Any "CRITICAL" test case..

Reply: remember to put null at the end of the string you print

Last edit: 2015-12-19 19:58:19
tarang219: 2015-12-17 15:04:52

firstly AC then on next day it changes to WA automatically

Reply: I rejudged all submission because a testcase was missing

Last edit: 2015-12-19 20:06:23
hmp: 2015-12-17 12:20:32

add to basic


Added by:Hussein Aassem
Date:2015-12-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY