小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n1, n2, · · · , nT 的木头。对于每个初始长度为 n 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。每次砍柴时，若当前木头长度为 x ，需要砍下一截长度为 p 的木头，然后换另一个人继续砍，其中 2 ≤ p ≤ x 且 p 必须为质数。当轮到某一方时 x = 1 或x = 0 ，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1 （数字 1），如果小乔赢请输出 0 （数字 0）。
输入的第一行包含一个正整数 T，接下来 T 行，每行包含一个正整数，其中第 i 的整数为 ni 。
输出 T 行，每行包含一个整数，依次表示对于每一根木头的答案。
3 1 2 6
0 1 1
【样例说明】
对于 n1 = 1 ，由于当前长度 x = 1 ，小蓝直接输掉，小乔赢；
对于 n2 = 2 ，小蓝选择 p = 2 ，轮到小乔时当前长度 x = 2 − 2 = 0 ，小乔输掉，小蓝赢；
对于 n3 = 6 ，小蓝选择 p = 5 ，轮到小乔时 x = 6 − 5 = 1 ，小乔输掉，小蓝赢。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ ni ≤ 103；对于所有评测用例，1 ≤ ni ≤ 105 ，1 ≤ T ≤ 104