LWAR - Lethal Warfare

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 2N -1), the strategy to be used, which we will call BombStrat, goes like this:

  1. Bomb its first half, [0 to 2N-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 2N-1, 2N-2 ... 2N-1+2N-2 in that order.
  3. Then use BombStrat on the remaining ships: [2N-1 to 2N-1 + 2N-2 -1]

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

  1. Ships 0, 1, 2, 3 get bombed in that order.
  2. Ships 7, 6 go down next.
  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

Input:
3
111
100
1100

Output:
100
110
1011

Added by:Prasanna
Date:2006-01-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06

hide comments
2021-10-28 17:14:50
Easy logic!!! AC in one go with 400B code in C++!!!
2010-05-23 18:50:08 Ravi Kiran
Nice tricky problem! :-)
Takes time to observe a way to avoid TLE!
If ur planning to give up on it,then mail me!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.