Similar Words

A non-empty sequence of lowercase English letters is called a word. A prefix of a word $x$ is a word $y$ that can be obtained from $x$ by removing zero or more of its last letters.

Two words are called 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 a set $X$ of non-empty words such that:

• every word in $X$ is a prefix of some word in $S$;
• $X$ contains no two similar words.

The input contains multiple test cases. The first line contains an integer $t$, the number of test cases. The descriptions of the test cases follow.

The first line of each description contains an integer $n$, the number of words in the set $S$ ($1 \le n \le 10^6$). Each of the following $n$ lines contains one non-empty word, an element of $S$. All words in $S$ are distinct.

The total length of all words in one input does not exceed $10^6$.

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