题目描述

有一天，谭谭在外面散步，她看到前方排了好长好长好长好长的队伍，谭谭惊奇的发现，她能看到每个人的头上都有一个数字，上面要么是1要么是0，谭谭就开始数 1,10,100,1000 ...  组成序列1101001000 。谭谭想知道第n个位置的人到底是1还是0，你能帮帮她吗？

输入格式

第1行：笨笨的谭谭一共会T个问题（1 第2 - T + 1行：每行1个数N。（1

输出格式

共T行，如果他是0，就输出0，如果他是1，就输出1。

3
1
2
3

1
1
0