問題文

作問者の loop0919 さんは、以下の問題を考えました。

Index × A Problem：

正整数 $l, r ~ (l \leq r)$ が与えられます。

以下の条件をすべて満たす数列 $A$ の長さの最大値を求めてください。

• $A$ の各要素は $l$ 以上 $r$ 以下の整数である。
• $i \times A_i ~ (1 \leq i \leq |A|)$ は一定である。

しかし、loop0919 さんはこの問題が既出かもしれないと思い、以下のように改題することにしました。

Sigma Index × A Problems：

正整数 $N$ が与えられます。
$f(l, r)$ を、この $l, r$ についての Index × A Problem の答えと定義します。

このとき、$\displaystyle \sum_{l = 1}^N \sum_{r = l}^N f(l, r)$ を $998244353$ で割った余りを求めてください。

正整数 $N$ が与えられるので、この $N$ に対する Sigma Index × A Problems の答えを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \leq T \leq 10^5$
• 各テストケースについて、以下の制約をすべて満たす。
• $1 \leq N \leq 10^{17}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。ここで $\mathrm{case}_t ~ (1 \leq t \leq T)$ は $t$ 番目のテストケースを表します。

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

各テストケースは以下の形式で与えられます。

$N$

出力

$T$ 行出力してください。$t$ 行目には $t$ 番目のテストケースについての答えを出力してください。

サンプル

5
3
16
256
1000000007
31415926535897932

8
247
77323
452669419
124925574