你是国际代码打印大赛（ICPC）决赛的参赛者。在到达试赛环节时，你发现与常规编程竞赛不同，任何队伍都可以发送代码给其他任何队伍进行打印！

主办方不希望产生额外的纸张费用，也不想检查消息中是否包含对题目解法的非法提示。因此，向另一支队伍发送文本打印必须满足以下条件：

• 如果 $S$ 是发送队伍的名称，$T$ 是接收队伍的名称，则发送打印的文本必须是 $S$ 和 $T$ 的公共非空子串；
• 一支队伍不能向同一支队伍发送两次相同的消息。

在比赛中解决问题固然很好，但出人意料地向对手发送消息也很有趣。你想知道在比赛期间，不同队伍之间最多可以传输多少条消息。

如果一条消息在几对有序的队伍之间传输，则应将其计入答案相应的次数。队伍为自己打印的消息不应计入答案。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

接下来是 $T$ 个测试用例的描述。每个描述的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示队伍的数量。

接下来的 $n$ 行，每行包含一个仅由小写拉丁字母组成的字符串 $S$ ($1 \le |S| \le 10^5$)，表示下一支队伍的名称。队伍名称可能相同。

保证所有测试用例中队伍的总数不超过 $10^5$，且所有测试用例中队伍名称长度之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数：不同队伍之间最多可以传输的消息数量。

样例

输入 1

2
2
abacaba
abc
5
dungeonthread
mediumrare
bsunumberseven
sostuffy
fiksiki

输出 1

8
52

说明

在第一个测试用例中，每支队伍可以向另一支队伍发送以下字符串：a, ab, b, c。

在第二个测试用例中，字符串 a, d, f, i, m, n, o, re, t, un, um 可以以两种方式发送，字符串 e, r, s 可以以六种方式发送，字符串 u 可以以十二种方式发送。