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

对于每个字符串 $s_i$，你有两种选择：

• 忽略这个字符串。此时该串的神圣值 $a_i = 0$。
• 从 $s_i$ 中选择一个与 $t$ 相等的子串。假设你选的这个子串为 $[L,R]$，那么 $a_i = L$。

你需要在选择至少两个串的前提下，最大化：

Input

第一行输入一个整数 $T$（$1 \le T \le 50$），表示测试的总数。

对于每个测试样例：

• 第一行输入一个数 $n$（$1 \le n \le 50$），表示字符串的个数。
• 接下来 $n$ 行，每行一个字符串 $s_i$（$1 \le |s| \le 10^5$）。

保证样例中 $\sum |s| \le 1.1 imes 10^6$。

Output

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

Sample

Input

2
3
a
aa
aaa
1
abc

Output

6
0

Hint

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