Let's consider an infinite sequence of digits constructed of ascending
powers of 10 written one after another. Here is the beginning of the sequence: 110100100010000… You are to find out what digit is located at the definite position of the sequence.
There is the only integer N in the first line (1 ≤ N ≤ 65535).
The i-th of N left lines contains the integer Ki — the number of position in the sequence (1 ≤ Ki ≤ 231 − 1).
You are to output N digits 0 or 1 separated
with a space. More precisely, the i-th digit of output is to be equal to the
Ki-th digit of described above sequence.
0 0 1 0
Problem Author: Alexey Lakhtin
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session