因子和奇偶性

题目描述

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

对于正整数 x，如果存在正整数 p 使得 x 能被 p 整除，则称 p 是 x 的因子。

输入格式

第一行输入一个整数 T，表示测试数据组数。

接下来 T 行，每行输入一个正整数 n。

输出格式

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

• 奇数输出 1
• 偶数输出 0

数据范围

1 <= T <= 2 * 10^4

1 <= n <= 10^18

样例 1

输入

5
1
2
3
4
8

输出

1
0
0
1
0