Longest Common Prefix

You are given a list of words for each test case. Your task is to find and return the longest common prefix shared among all the words in the list. If there is no common prefix, return an empty string.

The longest common prefix of a set of strings is the initial part (prefix) that is common to all strings. For example, for the words flower, flow, and flight, the longest common prefix is fl. If the words share no common prefix, output an empty string.

Note: In this problem, the overall input begins with an integer \(T\) representing the number of test cases. Each test case then starts with an integer \(n\) (the number of words) followed by \(n\) lines, each containing one word.

inputFormat

The input is read from stdin and has the following format:

T
n1
word1
word2
... 
word_n1
n2
word1
word2
... 
word_n2
...

Where:

• T is the number of test cases.
• For each test case, the first line is an integer \(n\) denoting the number of words.
• This is followed by \(n\) lines each containing a single word.

outputFormat

For each test case, print the longest common prefix on a new line to stdout. If a test case has no common prefix, print an empty line.

## sample

2
3
flower
flow
flight
3
dog
racecar
car

fl

</p>