Longest Common Substring

This problem requires you to find the longest common substring for each test case. For each test case, you are given a number of strings. Your task is to determine the longest substring that appears in every one of these strings.

A substring is a contiguous sequence of characters within a string.

Note: If there is no common substring among the strings, output an empty string.

Hint: A dynamic programming solution for two strings can be extended to handle multiple strings by taking pairwise longest common substrings.

The formula for updating the DP table is given by:

$$DP[i][j] = \begin{cases} DP[i-1][j-1] + 1, & \text{if } s_1[i-1] = s_2[j-1] \\ 0, & \text{otherwise} \end{cases} $$

inputFormat

The first line of input 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 following n lines each contain a string.

Constraints: 1 ≤ n, and strings can be assumed to have reasonable lengths.

outputFormat

For each test case, output a single line containing the longest common substring among the given strings. If no common substring exists, output an empty line.

## sample

4
3
abcd
abc
ab
2
xyz
yzx
2
abc
def
2
a
a

ab
yz
a

</p>