Bitstring v2

0-k és 1-esek egy végtelen sorozatát bináris sorozatnak nevezzük amennyiben az az 1, 2, 3, 4,... számok bináris alakjának összefűzéséből áll. (A bináris számok kiírásánál a lehető legkevesebb karaktert használjuk, így 1=1, 2=10, stb.) A sorozat eleje így decimális alakban 123456789101112, mely bináris számrendszerre átváltva 1101110010111011110001001101010111100. A feladatunk egyszerű: ebben a végtelen hosszú bináris sorozatban meg kell keresnünk a megadott indexeknél lévő 0, vagy 1 értékeket és kiírnunk azokat. A sorozat indexelése a 0. karakterrel kezdődik.

Input

Az input két egységből áll:

• Az első sor egy pozitív egész n szám, mely a kiírandó értékek számát adja meg.
• A következő n darab sor mindegyike 1-1 BINÁRIS számot tartalmaz. Ezek az indexek.

Output

Az output n sor, mely mindegyike egy 0, vagy 1 szám attól függően, hogy a bináris sorozat inputban megadott indexein milyen érték szerepel. Az input k-adik indexe az output k-adik sorának felel meg.

Megkötések

Példa