Description

有一个无穷数列，其通项表示为： ａn＝10^n， ｎ＝0，1，2，…… 构成了1，10，100，1000，……，把它连起来，就成了数串110100100010000……。 问题是如何知道这数串的第i位到底是0还是1。有数学天才的人可能思考起来容易一些，但不要忘了，现在是做程序，不是做数学。请把数学结论用于编程吧！

Input

第一个数占一行，是正整数N（N＜=100000），表明后面有N个正整数。后面N个正整数ki(i=1,2,3…N)都符合1≤ki≤2^31。

Output

输出每个0或者1的时候，都要换行。

Sample

Input

5
4
3
14
7
6

Output

1
0
0
1
0