A11247 | 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.

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<=10^{6}$ ). 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 $10^{6}$ .

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