Cannot parse: 1000 MS error parsing time

Description

小k和小f要加密通话，小f不会解密小k发出的加密信息，请你帮帮TA。 一个长度为$2^n-1$的01字符串s(从1开始编号）符合以下规则

for(int i=0;i<n;i++) {   int t=0;   for(int j=1;j<=(1<<n)-1;j++)   {     if((1<<i)&j) t=t^s[j];   }   字符串保证所有的结果t=0 }

小k发送上述字符串，但为了实现加密通话，小k会改变任意一位数，你能利用上述的规则来帮小f把正确的字符串输出吗？

Format

Input

第一行是一个整数T($7\leq T<1024$)代表要解密的字符串数目。 接下来的T行，每一行包含一个01字符串s，长度保证为$2^n-1$,n为整数($2\leq n< 10$)。

Output

输出T行，每一行输出解密后正确的字符串。

Samples

15
111110100100100
001110100100100
010110100100100
011010100100100
011100100100100
011111100100100
011110000100100
011110110100100
011110101100100
011110100000100
011110100110100
011110100101100
011110100100000
011110100100110
011110100100101

011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100
011110100100100