You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

聚光灯突然打在舞台角落，那个常年穿着格子衫的程序员突然清了清嗓子："咳咳，本世纪最憋屈配角奖得主——$1e9+7$同学！你每天帮别人防溢出防爆int，自己却连个专属题目都没有。今天我们要给你定制个逆天改命的舞台！"

定义一个类别，称为 “$10^9 + 7$类”。假设有一堆编号依次为 $1, 2, 3, \cdots, p$ 的小球，其中正整数 $p$表示小球的总数量。

对于这 $p$ 个小球中的每一个，我们设其编号为 $i$（$1 \leq i \leq p$），计算 $\left\lfloor \frac{10^9 + 7}{i} \right\rfloor$ 的值，其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整，也就是不超过 $x$ 的最大整数。

根据上述计算结果，将所有满足 $\left\lfloor \frac{10^9 + 7}{j} \right\rfloor = \left\lfloor \frac{10^9 + 7}{k} \right\rfloor$ 的正整数 $j$ 和 $k$（$1 \leq j, k \leq p$）所对应的小球归为同一类。也就是说，编号为 $j$ 和 $k$ 的小球，如果计算 $\left\lfloor \frac{10^9 + 7}{j} \right\rfloor$ 和 $\left\lfloor \frac{10^9 + 7}{k} \right\rfloor$ 的结果相同，那么这两个小球就属于同一类。

现在，对于输入的正整数 $p$（$1 \leq p \leq 10^9+7$），需要计算出所有分类的总数，然后对所有分类总个数进行异或运算（采用异或运算的目的是为了避免输出数量过多，从而防止在某些编程语言中出现超时的情况）。

注意,答案是所有分类总个数的异或,不是 $mod$ $10^9+7$,今天 $10^9+7$ 可是主角!

Input Format

第一行输入一个整数 $T$ （$1 \leq T \leq 500$）表示测试用例的数量

第二行$T$个整数 $p$（$1 \leq p \leq 10^9+7$），表示小球的总数量。

Output Format

输出$T$行整数，表示每个测试用例所有分类总个数的异或结果。

Sample

输入 #1

4
3
4
9
16

输出 #1

1
0
1
0

Hint

令$n=10^9+7$

$\left\lfloor \frac{n}{1} \right\rfloor=1000000007$

$\left\lfloor \frac{n}{2} \right\rfloor=500000003$

$\left\lfloor \frac{n}{3} \right\rfloor=333333335$

$\left\lfloor \frac{n}{4} \right\rfloor=250000001$

测试用例1:有三类 $[1000000007,500000003,333333335]$ ,每类有一个,异或结果 $1 \, \mathrm{XOR} \,1 \, \mathrm{XOR} \, 1 =1$

测试用例2:有四类 $[1000000007,500000003,333333335,250000001]$ ,每类有一个,异或结果 $1 \, \mathrm{XOR} \,1 \, \mathrm{XOR} \, 1 \, \mathrm{XOR} \, 1 =0$