D. Big Xor Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a big array $$$a$$$ of size $$$n$$$ and $$$a_i=i-1$$$.

Calculate $$$\Sigma _{1 \leq l \leq r \leq n}a_l \oplus a_{l+1} \oplus ...\oplus a_r$$$.

For example $$$n=4,a=[0,1,2,3]$$$,the answer is:

$$$0+1+2+3+(0\oplus1)+(1\oplus2)+(2\oplus3)+(0\oplus1\oplus2)+(1\oplus2\oplus3)+(0\oplus1\oplus2\oplus3)=14$$$.

Because the answer may be very large, output it modulo $$$998244353$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains an integer $$$n(1 \leq n \leq 10^9)$$$.

Output

For each test case, output on a new line:$$$\Sigma _{1 \leq l \leq r \leq n}a_l \oplus a_{l+1} \oplus ...\oplus a_r$$$(modulo $$$998244353$$$).

Example
Input
3
4
5
12345
Output
14
38
432693301