C. Binomial XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$M = 998244353$$$.

You are given an integer $$$n$$$. For an integer $$$i$$$ ($$$1 \le i \le n$$$), define $$$f(i)$$$ as follows: $$$$$$f(i) = \left(\binom{i}{i} \bmod M\right) \oplus \left(\binom{i+1}{i} \bmod M\right) \oplus \cdots \oplus \left(\binom{n}{i} \bmod M\right)$$$$$$

Formally, $$$$$$f(i) = \bigoplus_{j=i}^{n} \left(\binom{j}{i} \bmod M\right)$$$$$$

Here, $$$\binom{x}{y}$$$ denotes the binomial coefficient, which represents the number of ways to choose $$$y$$$ items from a set of $$$x$$$ items, and $$$\oplus$$$ denotes the bitwise XOR operation.

Note that to compute $$$f(i)$$$, you first compute the modulo operation on each binomial coefficient, then apply the XOR operation. You should not take $$$f(i) \bmod M$$$.

Please output $$$f(1) \oplus f(2) \oplus \cdots \oplus f(n)$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^6$$$) — the number of test cases.

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$).

Output

For each test case, output the answer.

Example
Input
2
2
1
Output
2
1
Note

In the first test case,

  • $$$f(1) = \left(\binom{1}{1} \bmod M\right) \oplus \left(\binom{2}{1} \bmod M\right) = 1 \oplus 2 = 3$$$
  • $$$f(2) = \left(\binom{2}{2} \bmod M\right) = 1$$$
So the answer is $$$f(1) \oplus f(2) = 3 \oplus 1 = 2$$$.

In the second test case,

  • $$$f(1) = \left(\binom{1}{1} \bmod M\right) = 1$$$
So the answer is $$$f(1) = 1$$$.