U370876 最长串

小a手中有 $n$ 个字符串，他希望能从中选出一些字符串，来拼接出一个最长的字符串。 拼接的要求是这样的，这 $n$ 字符串字符串是按照顺序给出的，假如 $i$ 位置的字符串 $S_i$ 想要与 $j$ 位置的字符串 $S_j$拼接，那么需要满足 $i < j$ 并且字符串 $S_i$ 的最后一个字符等于 $S_j$ 的第一个字符。 现在，请你告诉小a，这个拼接出来的字符串最长是多少。

第一行一个正整数 $T$ 表示数据组数。 对于每一组数据，第一行一个正整数 $n$ 表示字符串的个数。 接下来的 $n$ 行，每行一个字符串 $S_i$ 。

对于每一组数据，一个正整数表示拼接出来的字符串最长是多少。

**解释#1** 选择 $1,2,4,5$ 号字符串组合出长度为 $8$ 的字符串 $abbaaccb$ 。 **数据范围** 对于 $20\%$ 的数据，保证 $1\leq n \leq 10$ 。 对于另外 $20\%$ 的数据保证，$1\leq n \leq 10^3$ 。 对于 $100\%$ 的数据，保证 $1\leq n \leq 10^5, \ 1\leq T \leq 10$ 并且保证对于每一组数据保证 $\sum |S| \leq 2*10^6$ 。