Longest Common Subsequence Among Multiple Strings

Given T test cases, each test case consists of a list of strings. Your task is to compute the longest common subsequence (LCS) among all the strings in a test case. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

If there are several LCS of the same length, you may output any one of them. In the case where no common subsequence exists, output an empty string.

The solution should handle moderate input sizes efficiently.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 10), representing the number of test cases. For each test case, the first line contains an integer N (1 ≤ N ≤ 50), indicating the number of strings. This is followed by N lines, each containing one non-empty string made up of letters.

outputFormat

For each test case, print the longest common subsequence among the given strings on a separate line. If no common subsequence exists, output an empty line.

## sample

3
3
abcdef
abdfgh
abdf
2
xyz
wxyz
2
abc
def

abdf
xyz

</p>