Truck History

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, others for furniture, or for bricks. The company has its own code describing each type of truck. The code is a string of exactly seven lowercase letters (each letter in each position has a special meaning, but that is unimportant for this task). At the beginning of the company's history, just a single truck type was used, but later other types were derived from it, then from the new types other types were derived, and so on.

Today, ACM is rich enough to pay historians to study its history. One thing the historians tried to find out is the so-called derivation plan -- that is, how the truck types were derived. They defined the distance between two truck types as the number of positions at which their codes have different letters. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type, which was not derived from any other type). The quality of a derivation plan is defined as

$$\frac{1}{\sum_{(t_o, t_d)} d(t_o, t_d)}$$

where the sum is taken over all pairs in the derivation plan such that $t_o$ is the original type and $t_d$ is the type derived from it, and $d(t_o, t_d)$ is the distance between the two types.

Given the codes of the truck types, write a program that finds the highest possible quality of a derivation plan.

The input consists of several test cases. Each test case begins with a line containing the number of truck types $N$ ($2 \le N \le 2000$). Each of the following $N$ lines contains one truck type code (a string of seven lowercase letters). The codes uniquely describe the trucks: no two of the $N$ lines are the same. The input is terminated by a line containing a single $0$ in place of the number of truck types.

For each test case, output one line in the form The highest possible quality is 1/Q., where $1/Q$ is the quality of the best derivation plan and $Q$ is the smallest possible total distance over all valid derivation plans.