MOG
Spanish
|
English

Matcom Online Grader

ACM 2014 - Round #1

Ended

G - Pie Problem III

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (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