Minimal Word Search Tree Node Count

Given a list of words composed of uppercase English letters, you are required to construct the minimal word search tree (trie) with the following properties:

• The root node does not contain any letter.
• Every non-root node contains exactly one uppercase English letter.
• The word corresponding to a node is obtained by concatenating the letters along the path from the root to that node.
• Every word in the input list appears as the corresponding word of some node in the trie.
• The trie is constructed with as few nodes as possible.

Your task is to compute the total number of nodes in the trie, including the root node.

Mathematically, if T is the trie constructed from the set of words W, you need to find:

$$\text{Nodes}(T)$$

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10^5), representing the number of words. Each of the following n lines contains a word, consisting only of uppercase English letters, with length at most 100.

outputFormat

Output a single integer representing the total number of nodes in the minimal word search tree (including the root node).

sample

3
ABC
ABD
B

6