5200: 玩游戏
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：35
解决：11
题目描述
初始有一堆石子共n个，双方轮流行动，每次可以从中取出恰好完全平方数（1、4、9……）个石子，不可以不取石子直接跳过回合。双方都足够聪明，会按最优的方式来游玩，无法行动的人输掉该游戏（等价说法：取走最后一个石子的人赢）。
输入
样例个数t(1<=t<=1e6)
接下来t个n(1<=n<=1e6)
接下来t个n(1<=n<=1e6)
输出
对于每个n，如果先手赢了输出1，否则输出0
样例输入 复制
3
2
4
1029样例输出 复制
0
1
1