以前，没有电话的时候，进行快速远距离通信的主要手段是电报，即将所需要传送的文字转化成由二进制的字符组成的字符串。例如，假设需传送的电文为‘A B A C C D A’，它只有四种字符，根据字符出现的概率赋予每个字符一个权值（即字符在电文中出现的个数），比如：
A：3
B：1
C：2
D：1

此时我们有一种编码叫做Huffman编码可以对上述电文进行压缩（没有这个技术，人家可要多少你好多Money了！），现在要你完成Huffman编码，求出最后的平均码长。

输入数据有多组，第一行输入测试数据组数m。接下来的m行中，每行一个n值开头，代表电文中有多少种不同的字符，后面输入n个正整数，表示每个字符的权值。假设字符种数不超过100个（英文不够可以用中文嘛^_^）。

输出每组电文经过Huffman编码之后的平均码长，结果保留小数点后3位。

zj