题目描述

利用哈夫曼树可以产生哈夫曼编码。对于字符串 "SATSAACTATCSATAASAT"，图中方框的数表示对应字母的出现顺序，我们将出现次数最小的 C 和 S 先放在一起，他们的总出现次数为六，再将当前最小的 T 和 (CS) 放在一起，以此类推。然后，将数的左边记为 0，右边记为 1，就得到了每个字母的编码。可以证明，这样的编码无论怎么排列，都不会有歧义。

已知字符串 $S$，求出用哈夫曼编码后该字符串所占的位数。

输入格式

输入文件第一行将包含一个整数 $N$，接下来 $N$ 行，每行一个字符串 $S$。字符串将仅包含大写字母数字字符。

输出格式

每行一个整数，表示哈夫曼编码后该字符串所占的位数。

3
AAAAABCD
THE_WRITERS_ARE_HANDSOME
LUOGUYYDS

13
86
25

数据范围

对于 $30\%$ 的数据，$N \leq 5$。

对于 $100\%$ 的数据，$|S| \leq 1000，N \leq 20$。