Longest Common Prefix

Given an array of strings, your task is to find the longest common prefix string amongst them. The longest common prefix is defined as the initial segment that is shared by all the strings. If there is no common prefix, output an empty string.

For example, given the strings ['flower', 'flow', 'flight'], the longest common prefix is 'fl'; given ['dog', 'racecar', 'car'], there is no common prefix so an empty string should be printed.

The solution should read input from stdin and write output to stdout. Efficiency matters, so try to design a solution which minimizes unnecessary comparisons.

inputFormat

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

• The first line contains an integer T representing the number of test cases.
• Each test case begins with an integer N on a new line, indicating the number of strings.
• This is followed by N lines, each containing a single string.

outputFormat

For each test case, print a single line to standard output (stdout) containing the longest common prefix of the given strings. If there is no common prefix, print an empty line.

## sample

3
3
flower
flow
flight
3
dog
racecar
car
3
interspecies
interstellar
interstate

fl
inters

</p>