Fyz是一个商业领袖，手下有n个公司，没一个公司他有一个三位数编码，但是他现在想到了一种新的编码方式。
即原来的三位数的每一位数字0~9，对应成4位二进制编码，
例如1对应0001，2对应0010，5对应0101，9对应1001.
那么三位数（可能小于一百，默认前导为0）
例如 123 对应 000100100011
891 对应 100010010001
76对应 000001110110
5对应000000000101
初次之外，fyz为了让别人不觉得他的新编码太low，他要求上述编码后的二进制串进行首尾反转，并且去除前导0，作为最终编码。让你输出他每一个公司编码处理后的编码是什么？
第一行一个整数n，1<=n<=100
第二行n个整数a[i] , 0<=a[i]
<=999
n行，每一行代表a[i]对应的最终编码。