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.
Input
There is the only integer N in the first line (1 ≤ N ≤ 65535).
The ith of N left lines contains the integer K_{i} — the number of position in the sequence (1 ≤ K_{i} ≤ 2^{31} − 1).
Output
You are to output N digits 0 or 1 separated
with a space. More precisely, the ith digit of output is to be equal to the
K_{i}th digit of described above sequence.
Sample
input  output 

4
3
14
7
6
 0 0 1 0

Problem Author: Alexey Lakhtin
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session