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 K_i — the number of position in the sequence (1 ≤ K_i ≤ 2³¹ − 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 K_i-th digit of described above sequence.