题目内容

在一项语言学分析中，研究者收集了若干由小写字母构成的非空单词。他们发现，如果一个单词可以被拆分成两个非空部分，且这两部分恰好都是列表中已有的单词，那么它可能是一个复合词。由于列表中的单词可能有重复，需要保证参与组合的单词来自列表中的不同位置。

具体地，给定一个字符串序列 $s_1, s_2, \dots, s_n$，我们说 $s_i$ 是一个“可组合的”单词，当且仅当存在两个下标 $j$ 和 $k$（$j eq k$），使得 $s_j + s_k = s_i$，这里的 $+$ 表示字符串的拼接。等价地，存在一个切分位置 $p$（$1 \le p < |s_i|$），将 $s_i$ 分为前缀 $x = s_i[0:p]$ 和后缀 $y = s_i[p:]$，满足 $x$ 和 $y$ 都在列表中出现过，并且如果 $x = y$，则要求该字符串在列表中至少出现了两次。

请编写程序，对于给定的多组测试数据，分别统计每组中有多少个单词满足上述条件。

约束：

• 第一行输入的整数 $T$ 表示测试数据组数，满足 $1 \le T \le 2 \times 10^5$。
• 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。
• 所有测试数据中字符串长度之和不超过 $5 \times 10^5$。
• 每个字符串的长度至少为 $1$，且仅由小写字母组成。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 2 \times 10^5$），表示测试数据的组数。接下来依次给出每组数据，格式如下： 第一行一个整数 $n$，表示该组单词的数量。 接下来的 $n$ 行，每行一个字符串，由小写字母组成且长度至少为 $1$。

输出描述

对于每组测试数据，输出一行一个整数，表示该组中满足条件的可组合单词的数量。

样例1

输入

1
3
a
b
ab

输出

1

说明

列表中仅有 3 个单词："a", "b", "ab"。统计出现次数："a" 出现 1 次，"b" 出现 1 次，"ab" 出现 1 次。

对于 "ab"，长度为 2，唯一切分位置 $p = 1$ 将其分为前缀 "a" 和后缀 "b"。由于 "a" 与 "b" 不同，且两者在列表中都至少出现 1 次，满足可组合条件。

对于 "a" 和 "b"，长度均为 1，无法切分成两个非空部分，因此不可组合。最终答案为 1。

样例2

输入

1
4
a
a
aa
aaa

输出

2

说明

列表中有 "a", "a", "aa", "aaa"。出现次数："a" 出现 2 次，"aa" 出现 1 次，"aaa" 出现 1 次。

逐个判断：

• "a" 长度为 1，无法切分。
• 第二个 "a" 同理。
• "aa"：切分位置 $p = 1$ 得到左右部分都是 "a"，二者相同，需该字符串出现至少 2 次。而 "a" 实际出现 2 次，因此满足条件。
• "aaa"：切分 $p = 1$ 得 "a" 与 "aa"，两者不同且均存在（"a" 出现 2 次，"aa" 出现 1 次），满足条件；也可切分 $p = 2$ 得 "aa" 与 "a"，同样满足。

故 "aa" 和 "aaa" 均可组合，答案为 2。

样例3

输入

2
1
x
2
a
aa

输出

0
0

说明

第一组数据只有 "x"，长度为 1，无法切分为两个非空部分，答案为 0。

第二组数据有 "a" 和 "aa"。"a" 长度 1 不可切分；"aa" 切分后左右均为 "a"，二者相同，需要 "a" 在列表中出现至少 2 次，但 "a" 实际只出现 1 次，因此 "aa" 不可组合。答案为 0。

该样例展示了相同子串出现次数不足时的边界情形。