造桥

题号：NC234864
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

今天是愉快的周末，牛可乐和牛妹在一起玩游戏。牛妹给了牛可乐 $n$ 个造桥的零件，每个零件以字符串的形式给出，每个字符串两端的字符是零件的接口，两个零件可以通过连接不同端的接口（一个零件的左端只能连接另一个零件的右端，右端则只能连接左端）得到一个更长的零件，新零件的长度是原零件的长度之和。

牛妹规定，零件不能翻转，且零件左边的接口只能由该零件左边的零件去连接（这意味着，应该按顺序选取零件），右端同理。

牛可乐想得到牛妹的赞许，因此他要想用牛妹给的零件拼接一个尽可能长的桥梁，你能帮帮他吗？

第一行一个整数 $T$ ，代表案例数。

对于每一个案例：第一行一个数 $n$ ，表示字符串的个数。

接下来有 $n$ 行，每行一个字符串，每个字符串的长度 $\geq 2$ 。

$1 \leq T \leq 100$

所有案例的字符串长度的和不超过 $2 \cdot 10^5$ 。

保证所有字符均为小写字符。

$n$ 个字符串能拼接的最大字符串长度。

示例1

复制

1
6
ab
baabc
bb
ba
ba
ad

复制

按顺序依次拼接：1，3，5，6号字符串。