Longest Common Prefix

You are given a list of strings and your task is to find the longest common prefix among them. The longest common prefix is defined as the longest substring (LCP) that appears at the beginning of every string in the list. If there is no common prefix, output an empty string.

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

inputFormat

The input begins with an integer (T) representing the number of test cases. Each test case starts with an integer (n) — the number of strings in that test case — followed by (n) lines, each containing a single string comprised of lowercase English letters.

Example of a test case input:

T n string_1 string_2 ... string_n

outputFormat

For each test case, output the longest common prefix on a new line. If no common prefix exists, output an empty line.## sample

2
3
flower
flow
flight
2
dog
racecar

fl