Background

Asia 2002（Tehran, Iran）预赛题。

Description

给定若干个仅由字母组成且区分大小写的字符串。请找出一个最长字符串 (X)，使得对每一个给定字符串 (S)，都能在 (S) 中找到 (X) 或 (X) 的逆序串（reverse） 作为子串（连续片段）。 输出满足条件的最长 (X) 的长度。

Format

Input

第一行是整数 $t$$(1 \le t \le 10)$，表示测试用例数量。 接下来对每个测试用例：

• 第一行是整数 $n$$(1 \le n \le 100)$，表示给定字符串的数量；
• 接下来 $n$ 行，每行一个字符串：长度在 $1$ 到 $100$ 之间，只包含字母字符（区分大小写），且字符串行首行尾没有多余空白。

Output

对每个测试用例输出一行：满足条件的最长字符串 (X) 的长度。

Samples

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

2
2

Limitation

• $(1 \le t \le 10)$
• $(1 \le n \le 100)$
• 每个字符串长度：$(1 \sim 100)$