题目描述

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

• 桌子上有一堆石头。
• 你们轮流进行自己的回合， 你作为先手 。
• 每一回合，轮到的人拿掉 $1 \sim 3$ 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请判断你是否可以在给定石头数量为 $n$ 的情况下赢得游戏。如果可以赢，返回 $1$；否则，返回 $0$ 。

输入格式

第一行有一个整数 $T$，表示总共有 $T$ 次测试； 接下来有 $T$ 行，每行一个整数 $n$，表示给定的石头数量。

输出格式

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

**样例 **

样例输入#1

3
4
1
2

样例输出#1

0
1
1

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

1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3. 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。 在所有结果中，你的朋友是赢家。

提示：

对于 $100\%$ 的数据： $1 \le T \le 10^4,1 \le n \le 2^{31} - 1$；

其中 $10\%$ 的数据： $T=1， 1 \le n \le 10$；

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