WHX2025B. 游戏（nim）

题目描述

你和你的朋友nim，两个人一起玩一个游戏

桌子上有一堆石头。

你们轮流进行自己的回合， 你作为先手 。

每一回合，轮到的人拿掉 1∼3 块石头。

拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请判断你是否可以在给定石头数量为 n 的情况下赢得游戏。

如果可以赢，返回 1；

否则，返回 0 。

输入格式

第一行有一个整数 T，表示总共有 T 次测试；

接下来有 T 行，每行一个整数 n，表示给定的石头数量。

输出格式

共有 T 行，每行一个整数 0 或 1，表示答案。

**样例 **

样例输入#1

输入数据 1

3
4
1
2

输出数据 1

0
1
1

样例输出#1

解释： 以下是 n=4 可能的结果:

移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。

移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。

你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。 在所有结果中，你的朋友是赢家。

提示：

对于 100% 的数据：1≤T≤1e4,1≤n≤2^31 −1；

其中 10% 的数据： T=1，1≤n≤10；

其中 30% 的数据： T=5，1≤n≤100。