Autocomplete

Prerequisite: Trie Introduction

We receive the words in order. For each word, we first add it to the dictionary, then count how many characters the user must type before autocomplete can uniquely identify that word.

Autocomplete triggers as soon as the typed prefix matches exactly one word in the dictionary. If several words still share the prefix, the user must type another character. If the whole word is still not unique because it is a prefix of a longer word, the user types the whole word.

Example

words = ["hi", "hello", "bojack", "hills", "hill"]

Insert "hi" first. The dictionary has only one word, so typing "h" is enough: 1 stroke.

Insert "hello" next. Prefix "h" now matches both "hi" and "hello", but "he" matches only "hello", so this word costs 2 strokes.

Insert "bojack". Prefix "b" is unique, so it costs 1 stroke.

Insert "hills". Prefix "h" matches "hi", "hello", and "hills". Prefix "hi" still matches "hi" and "hills". Prefix "hil" is unique, so it costs 3 strokes.

Insert "hill". Prefixes "h", "hi", "hil", and "hill" are all shared with "hills" at the moment we insert it, so autocomplete never becomes unique before the word ends. The user types all 4 characters.

The total is 1 + 2 + 1 + 3 + 4 = 11.

Constraints

1 <= n <= 100001

The total length of all strings is at most 100001.

Words contain only lowercase letters and there are no duplicate words.