串串

Problem Description

给你 $n$（$1 \leq n \leq 50$）个仅有小写字母组成的字符串 $s_1, s_2, \cdots, s_n$，每个字符串的长度不一定相等。你需要选择一个字符串 $t$ （ $t$ 不一定在 $s$ 中选）。神圣值 $a$ 的定义如下：

• 对于每个字符串 $s_i$，你有两种选择：
• 忽略这个字符串。此时该串的神圣值 $a_i = 0$。
• 从 $s_i$ 中选择一个与 $t$ 相等的子串。假设你选的这个子串为 $[L, R]$，那么 $a_i = L$。 你需要在选择至少两个串的前提下，最大化 $$|t| \times \sum_{i = 1}^{n} a_i$$

Input

第一行输入一个整数 $T$（$1 \le T \le 50$），表示测试的总数。 对于每个测试样例， 第一行输入一个数 $n$（$1 \leq n \leq 50$） ，表示字符串的个数。 接下来 $n$ 行，每行一个字符串 $s_i$ （$1 \leq |s| \leq 10^5$）。保证样例中 $\sum |s| \leq 1.1 \times10^6$ 。

Output

对于每个样例，输出一个数，$|t| \times \sum_{i = 1}^{n} a_i$ 的最大值。若无法取到两个串，请输出 $0$。

Sample Input

2
3
a
aa
aaa
1
abc

Sample Output

6
0

Hint

对于第一个样例，我们选择 $t = aa$。这样神圣值可以选择为 $a$ = [0, 1, 2]。因此答案为 6。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）