Longest Common Prefix

Given T test cases, each consisting of an integer n and n strings, your goal is to determine the longest common prefix (LCP) among the n strings. The LCP is defined as the longest string ( S ) such that ( S ) is a prefix of every given string. If there is no common prefix, output an empty string.

For example, given the strings "apple", "apricot", and "ape", the longest common prefix is "ap".

inputFormat

The input is read from standard input (stdin).

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 second line contains n space-separated strings.

outputFormat

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

5
3
apple apricot ape
3
dog cat fish
2
banana band
3
orange orange orange
1
unique

ap
ban
orange
unique