問題文

正整数 $N$ が与えられます。

以下の条件を満たす $3$ 個の正整数の組 $(x,y,z)$ の個数を $998244353$ で割ったあまりを求めてください。

• $xy,yz,zx$ が全て $N$ 以下である。

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

制約

• $1 \\le T \\le 100$
• $1 \\le N \\le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

ここで、$\\mathrm{case}_i$ とは、$i$ 番目のテストケースを意味する。

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

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

$N$

出力

$T$ 行出力せよ。$i(1 \\le i \\le T)$ 行目には、$i$ 番目のテストケースに対する答えを出力せよ。

入力例 1

4
1
2
5
998244353

出力例 1

1
4
17
727512986

$1$ 個目のテストケースでは、$N=1$ です。条件を満たす $(x,y,z)$ は $(1,1,1)$ の $1$ 個です。

$2$ 個目のテストケースでは、$N=2$ です。条件を満たす $(x,y,z)$ は、$(1,1,1),(2,1,1),(1,2,1),(1,1,2)$ の $4$ 個です。