思路

我们要求解的目标是 $S = \sum_{i=1}^{n} \sigma(i)$ 的奇偶性，其中 $\sigma(i)$ 表示正整数 $i$ 的所有正因子之和。

一个和的奇偶性取决于其中奇数项的个数。如果奇数项的个数是奇数，那么和就是奇数；如果奇数项的个数是偶数，那么和就是偶数。因此，问题转化为：在区间 $[1, n]$ 中，有多少个整数 $i$ 使得 $\sigma(i)$ 是奇数。设这个数量为 $C$，我们最终要求的就是 $C \pmod 2$。

接下来我们分析 $\sigma(i)$ 为奇数的条件。 一个整数 $i$ 的标准素数分解为 $i = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$。 其正因子之和的公式为：

题目内容

给定一个正整数$n$。对于区间$[1,n]$，求区间内所有整数的正因子之和的奇偶性。

因子:对于正整数$x$，如果存在正整数$p$使得$x$能被$P$整除，则称$p$是$x$的因子。例如，$12$的因子有$1,2,3,4,6,12$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦2×10^4)$表示数据组数;

此后$T$行,每行输入一个整数$n(1≦n≦10^{18})$。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示区间$[1,n]$内所有整数的正因子之和的奇偶性：奇数输出$1$，偶数输出$0$

样例1

输入

5
1 
2
3 
4
8

输出

1
0
0
1
0

说明

• 当$n=1$时:$1$的因子只有$1$，总和为$1$(奇数)，输出$1$;
• 当$n=2$时:在$n=1$的基础上再加上$2$的因子 $1、2$，总和变为$4$(偶数)，输出$0$;
• 当$n=3$时:再加上$3$的因子$1、3$，总和变为$8$(偶数)，输出$0$;
• 当$n=4$时:再加上$4$的因子$1、2、4$，总和变为$15$(奇数)，输出$1$;