小苯的最短路

小苯有一个 $n$ 个点的无向完全图，编号从 $1$ 到 $n$，其中 $i$ 号点和 $j$ 号点之间的边权为 $i \oplus j$ 他想知道从 $1$ 号点出发到达所有点的最短路，请你帮他算一算吧。

输入

本题含有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据的组数，满足 $1 \leq T \leq 10^5$。

接下来 $T$ 行，每行一个正整数 $n$，表示完全图的点数，满足 $1 \leq n \leq 2 \times 10^9$。

输出

对于每组测试数据，输出一行一个正整数 $S$，表示到所有点的最短路的异或和。设 $d_i$ 表示从 $1$ 号点到 $i$ 号点的最短路，则有：

$$S = d_1 \oplus d_2 \oplus d_3 \oplus \cdots \oplus d_n$$

解答

其它过程过于简单不讨论，核心在于如何快速求得 $\bigoplus_{i=1}^{n} i$ 。

根据异或前缀和的性质，设 $f(n) = \bigoplus_{i=1}^{n} i$ ，有：

• 当 $n \mod 4 = 0$ 时，$f(n) = n$ 。

• 当 $n \mod 4 = 1$ 时，$f(n) = 1$ 。

• 当 $n \mod 4 = 2$ 时，$f(n) = n + 1$ 。

• 当 $n \mod 4 = 3$ 时，$f(n) = 0$ 。

因此可以 $O(1)$ 求得每组数据的答案。

switch(n) {
    case 0: 
        return n;
        break;
    case 1: 
        return 1;
        break;
    case 2: 
        return n + 1;
        break;
    case 3: return 0;
}