Minimal Trie Nodes Construction

Matej is facing a difficult problem. But before he can solve it, he must familiarize himself with the trie data structure. In a trie:

• Each edge is labeled with a letter from the English alphabet.
• The root node represents the empty prefix.
• Every other node represents a non-empty prefix, which is obtained by concatenating the labels on the path from the root to that node.
• No two edges originating from the same node have the same label.

Now, Matej is given n words, and he is allowed to rearrange (i.e. permute) the letters of some words arbitrarily. For example, the word "abc" can be rearranged into "acb", "bac", "bca", "cab", or "cba". Your task is to choose a reordering for each word so that when these words are inserted into a trie, the total number of nodes is minimized. Note that if the same word appears more than once (after reordering), it does not add extra nodes to the trie.

Mathematical formulation:

For each word, let \( w = c_1c_2\ldots c_m \) be rearranged as \( w' \) such that \( w' = \text{sort}(w) \) (i.e. its letters in non-decreasing order). Insert every \( w' \) into a trie. Let \( T \) be the set of nodes of the trie (including the root). Minimize \(|T|\).

Input Format: The first line contains an integer n (\(1 \leq n \leq 10^5\)), the number of words. Each of the following n lines contains a word consisting only of lowercase English letters. The total length of all words does not exceed \(10^6\).

Output Format: Print a single integer—the minimum number of trie nodes required.

inputFormat

The first line contains an integer n.

Each of the next n lines contains a word made of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of trie nodes after optimal rearrangement of each word.

sample

3
abc
bca
cab

4