B. 1e9+7

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

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

定义一个类别,称为 类”。假设有一堆编号依次为 的小球,其中正整数 表示小球的总数量。

对于这 个小球中的每一个,我们设其编号为 ),计算 的值,其中 表示对 向下取整,也就是不超过 的最大整数。

根据上述计算结果,将所有满足 的正整数 )所对应的小球归为同一类。也就是说,编号为 的小球,如果计算 的结果相同,那么这两个小球就属于同一类。

现在,对于输入的正整数 ),我们需要先计算出所有分类的总数,然后对所有分类总个数进行异或运算(采用异或运算的目的是为了避免输出数量过多,从而防止在某些编程语言中出现超时的情况)。

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

输入格式

第一行输入一个整数 )表示测试用例的数量

第二行个整数 ),表示小球的总数量。

输出格式

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

样例

输入 #1

4
3
4
9
16

输出 #1

1
0
1
0

数据范围与提示

测试用例1:有三类 ,每类有一个,异或结果

测试用例2:有四类 ,每类有一个,异或结果