Problem Description

Matej is faced with a challenging problem. Before we proceed, we need to familiarize ourselves with a data structure known as a prefix tree (trie). A prefix tree stores words in a prefix manner:

• Each edge in the prefix tree is represented by a letter from the English alphabet.
• The root node represents an empty prefix.
• Each other node represents a non-empty prefix. The prefix is obtained by concatenating the letters marked on the path from the root node to this node.
• There are no two edges with the same letter starting from one node.

For example, this prefix tree stores the words A, to, tea, ted, ten, i, in, inn:

Now, Matej has obtained $n$ words and can rearrange some of them. For example, abc can be rearranged into acb, bac, bca, cab, cba. Your task is to calculate the minimum number of nodes in the prefix tree that stores these words after rearranging some of them.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain a string representing one of Matej's words.

Output Format

Output a single integer, which is the minimum number of nodes in the prefix tree after rearranging some of the words.

Sample Input and Output

Sample Input #1

3
a
ab
abc

Sample Output #1

4

Sample Input #2

3
a
ab
c

Sample Output #2

4

Sample Input #3

4
baab
abab
aabb
bbaa

Sample Output #3

5

Notes

Sample 3 Explanation

All words can be rearranged into aabb. Clearly, the minimum number of nodes in the prefix tree should be $5$ (including the root node representing the empty prefix).

Data Size and Constraints

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

The total length of all words does not exceed $10^6$, and only lowercase letters are used.

Notes

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

见题面 Input 部分

见题面 Output 部分