H. Campo Grande
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During the programming marathon in Campo Grande in 2022, Jake Peralta and his friend Charles Boyle took the opportunity to visit the Bioparque Pantanal, one of the largest freshwater aquariums in the world. There, they were enchanted by the variety of fish of various species.

While observing the tanks, Jake had an idea for a game: Boyle would randomly choose a fish (with equal probability among all), and Jake would have to guess which one it was by asking only yes-or-no questions.

Jake could ask anything he wanted: "Does the name of the fish have an even number of letters?", "Does the fish have blue scales?", "Is the fish native to Brazil?", and so on...

Being extremely strategic, Jake decided to follow an optimal plan, minimizing the expected number of questions needed to discover the chosen fish. However, since he is not that good with calculations, he asked for your help. Your task is: given the list of names of the fish in the aquarium, all with distinct names, calculate the expected number of questions that Jake will need to ask if he uses the optimal strategy.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the number of fish.

The next $$$N$$$ lines contain the distinct names of the fish. Each name consists only of letters from the Latin alphabet (uppercase and/or lowercase). The total sum of the lengths of the names does not exceed $$$10^6$$$.

Output

Print the expected number of questions needed. The allowed absolute or relative error is at most $$$10^{-4}$$$.

Examples
Input
10
salmao
atum
sardinha
tilapia
bacalhau
panga
merluza
dourado
dori
nemo
Output
4.4000000000
Input
1
peixe
Output
1.0000000000
Input
2
atum
tilapia
Output
2.0000000000
Note

After narrowing down the options to just one fish, Jake still needs one turn to confirm his answer. For example, even when $$$N=1$$$, he must ask a question. See the examples for more details.