Problem Description
Two mathematicians Mr.X and Mr.Y are discussing about a problem. Mr.X says that the ans is a and Mr.Y says the ans is b(where a and b being string containing 0's and 1's). After arguing for a long time they find that Mr.X was giving the answer in binary code where as Mr.Y was giving the answer in Gray code. Mr.X wants to check if his ans matches with that of Mr.Y.

Help Mr.X find the gray code for his binary code.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains a single string a denoting the binary code

Output

For each test case, output a single line containing the Gray Code b.

Constraints

1 ≤ T ≤ 10000
1 ≤ |a| ≤ 1000

Example
Input:
3
100
011
10001

Output:
110
010
11001

见题面

见题面