Cellphone Keypad Autocomplete

Time limit1sMemory limit192 MB

Summary

For each word in a dictionary, compute how many letters a phone keypad must type when unique suffixes are autofilled, then print the average presses.

Level: Medium6 of 10
Topics: Trie, Tree, String, Implementation
Solved: No attempts yet

Problem

Typing an English word of length $P$ on a cellphone normally takes $P$ button presses. To speed this up, a researcher built a keypad module that uses a dictionary: whenever the prefix typed so far can be continued by only a single next letter across the whole dictionary, the module fills that letter in automatically, with no button press. The rules are:

The module never guesses the first letter. Even if every word in the dictionary starts with the same letter, the user must press that first letter.
Suppose the string $c_1 c_2 \cdots c_n$ (of length at least 1) has been entered. If there is a letter $c$ such that every dictionary word beginning with $c_1 c_2 \cdots c_n$ also begins with $c_1 c_2 \cdots c_n c$ , the module inputs $c$ automatically without a button press. Otherwise it waits for the user.

For example, suppose the dictionary contains the four words "hello", "hell", "heaven", and "goodbye". When the user presses "h", every word starting with "h" continues with "e", so the module fills in "e" automatically. But some words continue as "hel" and others as "hea", so the module now waits. When the user presses "l", the next letter is uniquely "l", so it is filled in automatically. However, "hell" ends here while "hello" does not, so the module waits again. To type "hell" the user stops here; to type "hello" the user must press "o". Thus "hello" needs 3 presses, and "hell" and "heaven" need 2 each ("heaven" only needs "a" after "he", after which everything is automatic). "goodbye" needs just 1 press, because after "g" every following letter is unique and is filled in to the end. The average number of button presses for these four words is $(3 + 2 + 2 + 1) / 4 = 2.00$ .

Given a dictionary, write a program that computes the average number of button presses needed to type each of its words with this module.

Input

The input consists of several test cases; process them in order until end of file.

The first line of each test case contains the number of words $N$ in the dictionary ( $1 \le N \le 10^5$ ). Each of the next $N$ lines contains one word made of lowercase English letters, with length between 1 and 80 inclusive. No word is given twice. Within a single test case, the total length of all words is at most $10^6$ .

Output

For each test case, print the answer on its own line, rounded to two decimal places.

Examples6

Example 1

Input

4
hello
hell
heaven
goodbye
3
hi
he
h
7
structure
structures
ride
riders
stress
solstice
ridiculous

Expected output

2.00
1.67
2.71

Example 2
Input
```
1
a
```
Expected output
```
1.00
```
Example 3
Input
```
1
programming
```
Expected output
```
1.00
```
Example 4
Input
```
2
ab
ac
```
Expected output
```
2.00
```
Example 5
Input
```
2
a
ab
```
Expected output
```
1.50
```
Example 6
Input
```
1
z
2
ba
bb
```
Expected output
```
1.00
2.00
```