你满心欢喜的召唤出了外星生物，以为可以变身超人拥有强大力量战胜一切怪兽，然而面对着身前高大的外星生物你一脸茫然，因为，你懂M78星云语吗？不过不用担心，因为零崎非常机智，他给出了关键性的提示：“讲道理，日语可是全宇宙通用语，所以为什么不试试和外星人讲日语呢？”
不过现在外星生物说的话都是“!@#$%^&%#%I&!……”这样的东西，你要怎么转换成日语呢？
作位全宇宙通用的日语，自然有一套万能的转换算法，那就是Huffman编码转换！当然了这肯定不是普通的Huffman编码转换，而是根据不同的编码长度转换为不同的假名。
第一行为一个整数t，接下来t行数据。1<=t<=100
每组输入数据为一个外星语字符串，为了表示方便，暂时使用大小写英文字母代替外星字母。字符串长度不超过2000
对于每组数据，输出对应的二进制Huffman编码总长度
2
abababac
abcdefg12
20