Rozpatrzmy nieskończony ciąg cyfr złożony z rosnących potęg 10 zapisanych jedna po drugiej. Początek takiego ciągu będzie wyglądał następująco: 110100100010000... Twoim zadaniem jest stwierdić jaka cyfra znajduje się na określonej pozycji w tym ciągu.

Wejście:

W pierwszej linii wejścia znajduję się liczba naturalna N < 65536. Kolejne N linii zawierają liczby naturalne i < 2^31 – numer pozycji w ciągu.

Wyjście:

Wyjściem powinno być N cyfr 0 lub 1 pooddzielanych spacją. i-ta cyfra powinna odpowiadać i-tej cyfrze w ciągu z i-tej pozycji wejścia.

Przykład:

Wejście:

4
3
14
7
6

Wyjście:

0 0 1 0