题目描述

给定 $n$ 个由小写英文字母构成的字符串 $S_1, S_2, \cdots, S_n$，称三个字符串 $S_a$，$S_b$ 和 $S_c$ 构成了一个三角形，若它们满足以下所有限制：

• $S_a + S_b > S_c$ 或 $S_b + S_a > S_c$。
• $S_a + S_c > S_b$ 或 $S_c + S_a > S_b$。
• $S_b + S_c > S_a$ 或 $S_c + S_b > S_a$。

这里的 $+$ 表示字符串连接操作。字符串通过字典序比较大小。例如，$\texttt{ba}$，$\texttt{cb}$ 和 $\texttt{cbaa}$ 构成了一个三角形，因为：

• $\texttt{cb}$ $+$ $\texttt{ba}$ $=$ $\texttt{cbba}$ $>$ $\texttt{cbaa}$.
• $\texttt{cbaa}$ $+$ $\texttt{ba}$ $=$ $\texttt{cbaaba}$ $>$ $\texttt{cb}$.
• $\texttt{cb}$ $+$ $\texttt{cbaa}$ $=$ $\texttt{cbcbaa}$ $>$ $\texttt{ba}$.

计算整数三元组 $(a, b, c)$ 的数量，满足 $1 \le a < b < c \le n$ 且 $S_a$，$S_b$，$S_c$ 构成了一个三角形。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 3 \times 10^5$）表示字符串的数量。

对于接下来的 $n$ 行，第 $i$ 行输入一个由小写字母构成的字符串 $S_i$（$1 \le |S_i| \le 3 \times 10^5$）。

保证单组数据所有字符串的总长度不超过 $3 \times 10^5$，所有数据所有字符串的总长度不超过 $10^6$。

输出格式

每组数据输出一行一个整数，表示合法的三元组数量。

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

16
0
0