Problem Statement

The problem setter, loop0919, came up with the following problem.

Index × A Problem:

You are given positive integers $l, r ~ (l \leq r)$.
Find the maximum length of a sequence $A$ satisfying all of the following conditions.

• Each element of $A$ is an integer between $l$ and $r$, inclusive.
• $i \times A_i ~ (1 \leq i \leq |A|)$ is constant.

However, loop0919 thought that this problem might have appeared before, and decided to modify it as follows.

Sigma Index × A Problems:

You are given a positive integer $N$.
Define $f(l, r)$ as the answer to the Index × A Problem for this $l, r$.

Find $\displaystyle \sum_{l = 1}^N \sum_{r = l}^N f(l, r)$ modulo $998244353$.

You are given a positive integer $N$. Find the answer to the Sigma Index × A Problems for this $N$.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 10^5$
• Each test case satisfies all of the following constraints.
• $1 \leq N \leq 10^{17}$
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_t ~ (1 \leq t \leq T)$ represents the $t$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$N$

Output

Print $T$ lines. The $t$-th line should contain the answer to the $t$-th test case.

Sample

5
3
16
256
1000000007
31415926535897932

8
247
77323
452669419
124925574