Problem 2B. p进制数2

时间限制：1000ms

空间限制：256MB

题目描述

在小\(G\)同学解决了\(p\)进制的取模问题之后，他又开始研究负数进制的问题，也就是说\(\sum w_i*p^i\)中的\(p < -1\).当然，小\(G\)同学喜欢从特殊到一般，所以他这次会研究\(-2\)进制的问题。他注意到

10	2	-2
-1	11	11
-2	10	10
-3	1101	1101

显然，\( -2\)进制可能与\(2\)进制的补码有很深的联系，于是他就请你帮忙。他希望每次向你询问一个\(2\)进制数的\(-2\)进制，而你只需要将它写出来。

数据格式

输入

第一行一个正整数\(T\)，表示测试用例的个数。

每个测试用例一行，一个\(01\)串表示一个有符号二进制数。最高位为符号位，参考c/c++的补码，可能包含前导零。

输出

每个测试用例一行，一个\(01\)串表示一个负二进制数，不得包含前导零。

样例

输入

5
00
01
11
10
1101

输出

0
1
11
10
1101

数据范围及约定

输入的\(01\)串不超过\(32\)位。