题目描述

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

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

例如:$12$的因子有$1,2,3,4,6,12$

输入描述

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

此后$T$行,每行输入一个整数$n(1\le n\le 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$;