B2 - Binárny reťazec

Napíšme si všetky prirodzené čísla, počnúc jednotkou, do jedného radu:

1 2 3 4 5 6 7 …

A prepíšme ich teraz do dvojkovej sústavy:

1 10 11 100 101 110 111 …

Vznikol nám jeden nekonečný reťazec zložený z núl a jednotiek.

Úloha

Vašou úlohou bude určiť, či sa na i-tom mieste tohto reťazca nachádza nula alebo jednotka.

Vstup

V prvom riadku je číslo N (1≤N≤10 000) – počet otázok. V každom z nasledujúcich N riadkov je jedno číslo i určujúce pozíciu v reťazci (pozície číslujeme od 1), ktorej hodnota nás zaujíma.

Výstup

Pre každú z N pozícií na vstupe vypíšte jeden riadok obsahujúci číslicu 0 alebo 1, ktorá sa nachádza na príslušnej pozícii reťazca.

B1

1≤i≤1 000 000

B2

1≤i≤10¹⁸

Príklad

Vstup

3
2
7
4

Výstup

1
0
1