题目描述

Advanced Cargo Movement有限公司使用不同类型的卡车。有些卡车用于运输蔬菜，有些用于运输家具或砖块。公司用特定的代码来描述每种卡车类型，该代码是一个由7个小写字母组成的字符串（每个位置上的字母都有特殊含义，但这对本题不重要）。在公司创立初期，只使用一种卡车类型，后来从该类型派生出其他类型，再从新类型派生出更多类型，依此类推。

如今，ACM公司财力雄厚，雇佣了历史学家研究其发展历史。历史学家试图找出所谓的"派生计划"——即卡车类型是如何派生的。他们将卡车类型之间的距离定义为两类型代码中不同字母位置的个数。他们还假设每种卡车类型都恰好从另一种类型派生而来（除了最初的卡车类型，它不是从任何其他类型派生的）。派生计划的质量定义为：

$1/Σ_{(t_o,t_d)}d(t_o,t_d)$

其中总和涵盖派生计划中所有类型对$(t_o,t_d)$，其中$t_o$是原始类型，$t_d$是从其派生的类型，$d(t_o,t_d)$是两类型之间的距离。

由于历史学家未能解决这个问题，你需要编写程序帮助他们。给定卡车类型的代码，你的程序应找出可能的最高质量派生计划。

输入格式

输入包含多个测试用例。每个测试用例以一行整数N开始（$2 ≤ N ≤ 2000$），表示卡车类型的数量。随后N行每行包含一个卡车类型代码（7个小写字母组成的字符串）。可以假设这些代码唯一描述卡车类型，即没有两行代码相同。输入以0表示测试用例结束。

输出格式

对于每个测试用例，程序应输出"The highest possible quality is 1/Q."，其中$1/Q$是最佳派生计划的质量。

输入输出示例

输入数据1

4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0

输出数据1

The highest possible quality is 1/3.

题目来源

CTU Open 2003