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 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^{N1} 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^{N1}+2^{N2} in that order.
3. Then use BombStrat on the remaining ships: [2^{N1} to 2^{N1} + 2^{N2} 1 ]
For example, when N=3, i.e., with ships numbered from 0 to 2^{3} 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 0based 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
Sample Input:
3
111
100
1100
Sample Output:
100
110
1011
hide comments
Ravi Kiran:
20100523 18:50:08
Nice tricky problem! :)

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