该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师有$n$个同学的姓名（仅由小写字母组成），他想知道这些姓名的最长公共前缀是什么。

例如姓名["flower", "flow", "flight"]，最长公共前缀为"fl"。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$。

接下来$n$行，每行一个仅包含小写字母的字符串。保证所有字符串的长度之和不超过$10^5$。

Output

对于每组数据，输出一行一个字符串，表示最长公共前缀。如果没有公共前缀则输出空行。

Samples

2
3
flower
flow
flight
2
dog
cat

fl

Limitation

1s, 1024KiB for each test case.