Longest Common Prefix

You are given T test cases. For each test case, you are provided with an integer N followed by N strings. Your task is to determine the longest common prefix among these strings. If no common prefix exists, output an empty string.

For example, if the strings are "flower", "flow", and "flight", the longest common prefix is "fl".

The expected time complexity is typically $O(N \cdot L)$ where $N$ is the number of strings and $L$ is the average length of the strings.

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains an integer T, the number of test cases.
• For each test case:
• The first line contains an integer N, the number of strings.
• The next N lines each contain a single string consisting of lowercase letters.

outputFormat

For each test case, output a single line to stdout containing the longest common prefix. If there is no common prefix, output an empty line.

## sample

2
3
flower
flow
flight
3
dog
racecar
car

fl

</p>