世界上充满了巧合。我们把每句话当成一个字符串，我们定义 $a$ 对 $b$ 的巧合值为a的最长后缀的长度并且它是恰好是 $b$ 的前缀，这里的后缀或者前缀包括字符串的本身。

比如字符串“天空仍灿烂她喜欢大海”对“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”的巧合值为 $5$ ，而字符串“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”对“天空仍灿烂她喜欢大海”的巧合值为 $2$。

现在给出 $n$ 个字符串由 ab 构成的字符串 $s_1,s_2,...,s_n$，求出对于所有 $1≤ i,j≤ n$，$s_i$ 对 $s_j$ 的巧合值的和。

第一行一个整数 $T\ (T≤ 1000)$，表示数据组数。

每组数据第一行一个正整数 $n\ (1≤ n≤ 10^5)$。

接下来 $n$ 行每行一个字符串 $s_i$，保证字符串由 ab 构成。

保证单组数据有 $\sum |s_i|\leq 1.5\times 10^6$，保证所有数据有 $\sum |s_i|\leq 5.5 \times 10^6$。