G - Pie Problem III

Time limit: 2 s
Memory limit: 128 MiB
Languages: C, C++, Java, JavaScript, ... (details)

Una secuencia de ceros y unos es generada de la siguiente manera: Un cero es escrito – este es el primer elemento de la secuencia. Entonces se añade la propia secuencia pero invertida. Así, después de cada paso, la secuencia duplica su tamaño. Es mostrado aquí cómo es formada la secuencia:

0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Escribe un algoritmo que determine el elemento $N$ de la secuencia.

Input

Línea 1 : Un entero $T$ representado la cantidad de casos $(1 \leq T \leq 50000)$. 
Línea 2…T+1 : Un entero $N$ $(1 \leq N \leq 10^{15})$ por línea.

Output

Línea 1…T : $0 / 1$ – El $N$-ésimo miembro de la secuencia.

Sample test(s)

Input
5 1 10 9 19191 3
Output
0 0 1 1 1

Hints