P14238 [CCPC 2024 Shandong I] 三角形

给定 $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$。

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