"She loves me", "She loves me not", "She loves me", "She loves me not", OH WAIT, I'm LALA,
"They love me", "They love me not", "They love me", "They love me not". Lala was indeed overwhelmed by the
'runner's high' and the turbulence inside him. Heart-broken by one of his many lalis, he decided to code out his frustration,
and also having read somewhere that some specific amount of 'so-called high' heightens brain power and creativity.
He thinks of making a large palindrome, using the formula
S(n)=S(n-1)+"0"+reverse(S(n-1))
but instead makes it up as
S(n)=S(n-1)+"0"+switch(reverse(S(n-1)))

After lala's passing out, in came patrick and wanted to check out what lala has done. Due to his over-technical abilities,
lala has encrypted the code such that at a time only the kth digit of the string will be visible.
As lala is lala, he has taken the upper limit to a whole another level and has coded it for 10^100.
As a programmer you are asked to fill in lala's shoes and code the program generating the kth digit for the last string.

The digits used are 0 and 1 and the functions are as follows:
switch:
the digit will be interchanged (0 for 1, 1 for 0)
reverse:
the string will be reversed.
Input
The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.
Output
For each test case, output one line containing is the Kth character of S

SAMPLE INPUT
4
1
2
3
10

SAMPLE OUTPUT
0
0
1
0

见题面

见题面