CF856B.Similar Words

Let us call a non-empty sequence of lowercase English letters a word. Prefix of a word x is a word y that can be obtained from x by removing zero or more last letters of x.

Let us call two words similar, if one of them can be obtained from the other by removing its first letter.

You are given a set S of words. Find the maximal possible size of set of non-empty words X such that they satisfy the following:

• each word of X is prefix of some word from S;
• X has no similar words.

我们称一个非空的小写英文字母序列是一个单词。单词 $x$ 的前缀是指一个单词 $y$，它可以通过从 $x$ 中移除零个或多个末尾字母而得到。

我们称两个单词是相似的，如果其中一个可以通过移除另一个单词的首字母而得到。

给定一个单词集合 $S$。请找出满足以下条件的非空单词集合 $X$ 的最大可能大小：

• $X$ 中的每个单词都是 $S$ 中某个单词的前缀；
• $X$ 中不存在相似的单词。

Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases. The descriptions of test cases follow.

The first line of each description contains an integer n — the number of words in the set S (1 ≤ n ≤ 106). Each of the following n lines contains one non-empty word — elements of S. All words in S are different.

It is guaranteed that the total length of all words in one input data doesn't exceed 106.

输入数据包含多个测试用例。输入数据的第一行包含一个整数 $t$ —— 测试用例的数量。随后是各测试用例的描述。

每个测试用例描述的第一行包含一个整数 $n$ —— 集合 $S$ 中单词的数量（$1 \le n \le 10^6$）。接下来的 $n$ 行每行包含一个非空单词 —— 即 $S$ 的元素。集合 $S$ 中的所有单词互不相同。

保证单组输入数据中所有单词的总长度不超过 $10^6$。

For each test case print one line that contains one integer m — the maximal number of words that X can contain.

对于每个测试用例，输出一行，包含一个整数 $m$ —— 即 $X$ 所能包含的单词的最大数量。