E. Binary Banter: Counting Combinatorial Bits
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a positive integer $$$n$$$, compute the value of the following expression modulo $$$998244353$$$:

$$$$$$ \sum_{i=0}^n\sum_{j=0}^i\left(C_i^j \bmod 2\right) $$$$$$

Where:

  • The binomial coefficient $$$C_i^j$$$ is defined as:

    $$$$$$ C_i^j = \begin{cases} \frac{i!}{j!(i - j)!}, & \text{if } 0 \leq j \leq i \\ 0, & \text{if } j \gt i \end{cases} $$$$$$

  • The factorial $$$m!$$$ is defined as the product of all positive integers from $$$1$$$ to $$$m$$$:

    $$$$$$ m! = \begin{cases} 1, & \text{if } m = 0 \\ 1 \times 2 \times 3 \times \dots \times m, & \text{if } m \geq 1 \end{cases} $$$$$$

  • The modulo operation $$$x \bmod y$$$ returns the remainder when $$$x$$$ is divided by $$$y$$$. For example:

    $$$$$$ 5 \bmod 2 = 1,\quad 8 \bmod 3 = 2,\quad 7 \bmod 7 = 0 $$$$$$

You need to output the value of the expression modulo $$$998244353$$$.

Input

There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 3 \times 10^5)$$$, denoting the number of test cases. For each test case:

The first and only line contains one integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.

Output

For each test case, output one line containing one integer, denoting the value of the expression modulo $$$998244353$$$.

Example
Input
3
3
5
1145141919810
Output
9
15
516911908
Note

For the first sample test case, $$$n = 3$$$, so you need to compute the following expression:

$$$$$$ \sum_{i=0}^{3} \sum_{j=0}^{i} \left( C_i^j \bmod 2 \right) $$$$$$

Let's analyze each row of binomial coefficients modulo $$$2$$$:

  • $$$i = 0$$$: $$$C_0^0 = 1 \Rightarrow 1 \bmod 2 = 1$$$
  • $$$i = 1$$$: $$$C_1^0 = 1$$$, $$$C_1^1 = 1 \Rightarrow 1 + 1 = 2$$$
  • $$$i = 2$$$: $$$C_2^0 = 1$$$, $$$C_2^1 = 2$$$, $$$C_2^2 = 1 \Rightarrow 1 + 0 + 1 = 2$$$
  • $$$i = 3$$$: $$$C_3^0 = 1$$$, $$$C_3^1 = 3$$$, $$$C_3^2 = 3$$$, $$$C_3^3 = 1 \Rightarrow 1 + 1 + 1 + 1 = 4$$$

So the total sum is $$$1 + 2 + 2 + 4 = 9$$$. And you need to output $$$9 \bmod 998244353 = 9$$$.

For the second sample test case, $$$n = 5$$$, so you need to compute the following expression:

$$$$$$ \sum_{i=0}^{5} \sum_{j=0}^{i} \left( C_i^j \bmod 2 \right) $$$$$$

Similarly:

  • $$$i = 0$$$: $$$1$$$
  • $$$i = 1$$$: $$$1\ 1$$$ $$$\Rightarrow$$$ sum = $$$3$$$
  • $$$i = 2$$$: $$$1\ 0\ 1$$$ $$$\Rightarrow$$$ sum = $$$5$$$
  • $$$i = 3$$$: $$$1\ 1\ 1\ 1$$$ $$$\Rightarrow$$$ sum = $$$9$$$
  • $$$i = 4$$$: $$$1\ 0\ 0\ 0\ 1$$$ $$$\Rightarrow$$$ sum = $$$11$$$
  • $$$i = 5$$$: $$$1\ 1\ 0\ 0\ 1\ 1$$$ $$$\Rightarrow$$$ sum = $$$15$$$

Final result: $$$(1 + 2 + 2 + 4 + 2 + 4) \bmod 998244353 = 15$$$

For the third sample test case, I have a brilliant explanation, but the space here is too small to writ