Problem C: 0's and 1's

John was bored so after a while of thinking he invented a kind of game.
He took a piece of paper and wrote 0 and 1 on it. Then he took the array he had already written and wrote a new array at the of it. The appended array had the same length as the original one, but had all 0's changed to 1's and 1's to 0's. So on the paper appeared 0110. John repeated the operation and had 01101001 on his paper.

John started to wonder what number is on the 20th position. He repeated the operation twice more (getting 01101001100101101001011001101001) and found out that there is 1 on this position.
Then John wanted to know what is on 200th position. After a few minutes of writing he knew it. But his young, curious mind made him wonder what is on 2.000.000th or even 2.000.000.000th position. So he started eagerly writing his arrays...
Unfortunatelly John did not realize that this way he would run out of paper (and of life perhaps) before he could get to the solution.

Please, help John and introduce an effective way of solving his problem.

Input data

At the begining of input there is one positive integer d, which is foollowed by d integers (not less than 1 and not greater than 2.000.000.000) - positions that John is interested in.

Output data

On output write d integers (each in separate line) - numbers on specified positions in the array.

Input data example:

3
1
5
20

Output data for our example:

0
1
1