说明

看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已！吴志国大队长在受了残忍的“针刑”之后躺在手术台上唱空城计，变了音调，把消息传给了护士，顾晓梦在衣服上缝补了长短不一的针脚……那么，片中无处不在的摩尔斯码到底是什么？它又有着怎样的神秘力量呢？

摩尔斯电码（Morse code）由点dot（. ）、划dash（-）两种符号组成。它的基本原理是：把英文字母表中的字母、标点符号和空格按照出现的频率排序，然后用点和划的组合来代表这些字母、标点符号和空格，使频率最高的符号具有最短的点划组合。哈夫曼编码又称最佳前缀码，频率高的编码短，而且一个字符编码不是另一个字符编码的前缀。现有n个字符及其出现的频率，求每个字符的哈夫曼编码。

输入格式

第一行是一个整型数$m$,表示共有$m$组测试数据。

每组测试数据的第一行是一个整数$n$表示该测试数据共有n个字符。

随后的n行，每行有一个字符$c_i$和一个浮点数$w_i$，表示字符$c_i$的出现频率为$w_i$。

输入数据保证每组测试数据的字符不会重复。

输出格式

对于每一组输入，输出n个字符及其01编码。

每组的输出占一行。

输出格式请参照样例。

注意：字符频率相同的，输入序号小的排前面。

样例

3
6
a 0.05
b 0.32
c 0.18
d 0.07
e 0.25
f 0.13
4
a 0.23
b 0.05
c 0.45
d 0.27
4
b 0.23
d 0.05
f 0.45
i 0.27

a: 1000 b: 11 c: 00 d: 1001 e: 01 f: 101
a: 111 b: 110 c: 0 d: 10
b: 111 d: 110 f: 0 i: 10

数据范围

• $m<100$
• $1<n<10000$

来源

《趣学算法》2.6节