本题的简单版本和困难版本是不同的问题，但请务必在通过本题后保留你的代码，因为它在后续可能会有用。

许多地名之间存在相似性。例如，Suzhou 和 Quzhou 被认为是相似的，因为它们拥有共同的子串 uzhou。子串是指字符串中连续的字符序列。例如，在字符串 abcd 中，bc 是它的一个子串，而 ac 则不是。

我们定义两个字符串之间的相似度为它们的最长公共子串的长度。因此，Suzhou 和 Quzhou 的相似度为 5，而 Hangzhou 和 Chengdu 的相似度为 2。

给定 $n$ 个地名，你的任务是找出其中相似度最大的两个地名，并输出该相似度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 15$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 50$)，表示地名的数量。接下来的 $n$ 行，每行包含一个字符串 $s$ ($1 \le |s| \le 50$)，表示地名。保证地名仅由小写英文字母组成。

保证所有测试用例中 $n$ 的总和不超过 300。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最大相似度。

样例

输入 1

2
2
jiangsu
xiangtan
3
hangzhou
chengdu
wuxi

输出 1

4
2