A major cosmic battle was getting over. The InterGalactic SuperPower had been under attack, but it had defended itself quite well. It was about to launch its final retaliatory assault. But the number of enemy ships was quite large and they could scatter very easily. Their only hope, or so their Space Warfare expert said, was to bomb the enemies (who happened to be lined up in a long line!) using the strategy described below.

Because the number of ships will be a power of 2, to bomb all the ships (numbered 0 to 2^N -1), the strategy to be used, which we will call BombStrat, goes like this:
1. Bomb it’s first half, [0 to 2^N-1 -1], in the left to right direction.
2. Of the remaining half, bomb its latter half part in reverse direction, i.e., bomb ships 2^N-1, 2^N-2,...., 2^N-1+2^N-2 in that order.

3. Then use BombStrat on the remaining ships: [2^N-1 to 2^N-1 + 2^N-2 -1 ]</p>

For example, when N=3, i.e., with ships numbered from 0 to 2³ -1, this is what happens:

Step 1: Ships 0,1,2,3 get bombed in that order.
Step 2: Ships 7, 6 go down next.
Step 3: Now, the remaining ships [4, 5] are destroyed using the same strategy.

So the bombing is done in the order 0 -> 1 -> 2 -> 3 ->

7 -> 6 -> 4 -> 5. To make the job easier for the InterGalactic SuperPower’s ships’ pilots, they want to find which ship should be bombed when. This is your task. Given N, and the description of a ship, return the 0-based serial number of the bomb will blast it.

Input

T – the number of test cases, T<=50.
For each test case:

One line containing a binary number, describing the number of the place. The length of this string will equal N (it will be padded with leading zeroes if necessary). N<=30000.

Output

For each test case, output the index of a bomb, represented in the same format, as binary digits, whose length is exactly N.

Example