给定 $n$ 个由小写英文字母组成的字符串 $S_1, S_2, \dots, 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$。

其中 $+$ 表示字符串拼接操作，字符串比较采用字典序。例如，ba、cb 和 cbaa 构成一个三角形，因为：

• cb + ba = cbba > cbaa。
• cbaa + ba = cbaaba > cb。
• cb + cbaa = cbcbaa > ba。

请计算满足 $1 \le a < b < c \le n$ 且 $S_a, S_b, S_c$ 构成三角形的整数三元组 $(a, b, 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$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件的有效三元组数量。

样例

输入 1

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

输出 1

16
0
0