1, 10, 100, 1000...

http://acm.timus.ru/problem.aspx?space=1&num=1209

Time Limit: 1.0 second

Memory Limit: 1 000 KB

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.

1. Input

There is the only positive integer number N in the first line, N < 65536. The i-th of N left lines contains the positive integer Ki - the number of position in the sequence. It's given that Ki < 231.

2. Output

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.

3. Sample Input