### 问题描述 蓝桥 A 梦和 Ity 玩游戏，游戏的规则是这样的： 1. 一共有 $N$ 颗瓜子，由 Ity 先手、蓝桥 A 梦后手，二人轮流进行操作。 2. 轮到某个玩家进行操作时，假设当前还剩下 $X$ 颗瓜子，该玩家可以选择 $X$ 各个数位上的数字中的某个非 $0$ 数字 $t$，并吃掉 $t$ 颗瓜子。 >比如在某一回合轮到蓝桥 A 梦进行操作，当前剩余的瓜子数量是 $830272$，那么蓝桥 A 梦可以选择吃掉$2$、$3$、$7$、$8$ 颗瓜子。假设蓝桥 A 梦选择吃掉 $8$ 颗瓜子，她完成操作后，场上将会剩余 $830264$ 颗瓜子。此时轮到 Ity 进行操作，她可以选择吃掉 $2$、$3$、$4$、$6$ 或者 $8$ 颗瓜子。（当然这里蓝桥 A 梦做出的决策可能不是最优的。） 3. 当场上没有瓜子时，吃掉最后一颗瓜子的玩家取得游戏的胜利。 假设他们都绝对聪明，使用最优策略，请预测谁将会取得游戏的胜利。 ### 输入格式 第一行一个正整数 $T$，表示有 $T$ 组测试数据。 以下 $T$ 行，每行一个正整数 $N$，表示假设游戏的最初有 $N$ 颗瓜子。 ### 输出格式 $T$ 行，每行一个字符串，表示你对游戏结果的预测。 如果你认为蓝桥 A 梦会赢，输出 `1`，否则输出 `0`。 ### 样例输入 ```text 3 1 10 230120 ``` ### 样例输出 ```text 0 1 1 ``` ### 评测数据规模 $T\le 2\times 10^5,1\le N\le 10^9$。