Description

Matej is facing a hard problem. Before that, we need to be familiar with a data structure called a prefix tree (trie). A trie stores words by their prefixes:

• Each edge in the trie is labeled with a letter of the English alphabet.
• The root node represents the empty prefix.
• Every other node represents a non-empty prefix. The prefix is obtained by concatenating the letters on the path from the root to that node.
• From any node, there are no two edges with the same letter.

For example, this trie stores A,to,tea,ted,ten,i,in,inn:

Now, Matej has obtained $n$ words, and he may reorder the letters of some of them. For example, abc can be reordered into acb,bac,bca,cab,cba. Please compute the minimum possible number of nodes in the trie that stores these words, after reordering some words.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain a string, representing a word that Matej has obtained.

Output Format

One line with one integer, the minimum possible number of nodes in the trie that stores these words after reordering some words.

3
a
ab
abc 

4 

3
a
ab
c 

4 

4
baab
abab
aabb
bbaa 

5 

Hint

Explanation for Sample 3

All words can be reordered into aabb. Clearly, the minimum number of nodes in the trie should be $5$ (including the root node that represents the empty prefix).

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 16$.

The sum of the lengths of all words does not exceed $10^6$, and all words contain only lowercase letters.

Note

This problem is translated from COCI2016-2017 CONTEST #1 T6 Vještica。

Translated by ChatGPT 5