砍柴

题号：NC309552
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小蓝和小乔正在森林里砍柴，它们有 $T$ 根长度分别为 $n_1, n_2, \cdots, n_T$ 的木头。对于每个初始长度为 $n$ 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。每次砍柴时，若当前木头长度为 $x$ ，需要砍下一截长度为 $p$ 的木头，然后换另一个人继续砍，其中 $2 \le p \le x$ 且 $p$ 必须为质数。当轮到某一方时 $x=1$ 或 $x=0$ ，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢输出 1（数字 1），如果小乔赢输出 0（数字 0）。

输入描述:

输入的第一行包含一个正整数 。

接下来  行，每行包含一个正整数，其中第  行的整数为 。

输出描述:

输出  行，每行包含一个整数，依次表示对于每一根木头的答案。

示例1

输入

复制

输出

复制

0
1
1

说明

对于 ，由于当前长度 ，小蓝直接输掉，小乔赢；

对于 ，小蓝选择 ，轮到小乔时当前长度 ，小乔输掉，小蓝赢；

对于 ，小蓝选择 ，轮到小乔时 ，小乔输掉，小蓝赢。

备注:

- 对于 20% 的评测用例，；
- 对于所有评测用例，。