题目描述

小Z了解了异或的运算规则：

$1\oplus0=1,1\oplus1=0,0\oplus0=0$

他手头刚好有一个只有点权的无向完全图，节点 $i$ 的点权即为 $i$。他打算把每个边权定义为左右端点的异或和。即：$i\xleftrightarrow{i\oplus j}j$。

小Z想知道从 $1$ 出发，到所有点的最短路（包括 $1$ 本身），输出这些结果的异或和。

输入格式

第一行，一个正整数 $q$，表示数据组数

每组数据一行，一个正整数 $n$，表示点数

输出格式

$q$ 行，每行表示第 $i$ 个图中，从 $1$ 出发到所有点的最短路值的异或和

输入输出样例

3
1
2
4

0
3
4

样例 $\tt \#1$说明

对于第二组数据，$d_i$ 表示从 $1$ 出发的最短路值：

$d_1 = 0, d_2=3$

所以结果为 $d_1\oplus d_2=3$

数据范围

$20\%:q\le 5,n\le 2000$

$50\%:q\le 50,n\le 10^6$

$100\%:1\le q\le 10^5,1\le n\le 2\times10^9$