jieti

#include<bits/stdc++.h>
using namespace
std;
using i64 = long long
;

namespace
myMath {
i64 mod =
998244353
;

i64 add(i64 x, i64 y) 

{
x += y;
if
(x > mod) x -= mod;
return
x;
}

i64 sub(i64 x, i64 y) 

{
x -= y;
if (x < 0
)x += mod;
return
x;
}

i64 mul(i64 x, i64 y) 

{
x *= y;
x -= x / mod * mod;
return
x;
}

i64 qpow(i64 x, i64 y) 

{
i64 res =
1
;
while
(y) {
if (y & 1) res = mul
(res, x);
y >>=
1
;
x =
mul
(x, x);
}
return
res;
}

i64 inv(i64 x) 

{
return qpow(x, mod - 2
);
}

i64 qdiv(i64 x, i64 y) 

{
return mul(x, inv
(y));
}

void set_mod(i64 x) 

{
mod = x;
}

namespace

Comb {
int
n;
vector<i64> fa;
vector<i64> ifa;

void init(int _n) 

{
n = _n;
fa.
assign(n + 1, 1), ifa.assign(n + 1, 1
);
for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1
], i);
ifa[n] =
inv
(fa[n]);
for (i64 i = n - 1
; i; i--) {
ifa[i] =
mul(ifa[i + 1], i + 1
);
}
}

    i64 C(int i, int j) 

{
return mul(fa[i], mul
(ifa[j], ifa[i - j]));
}

    i64 iC(int i, int j) 

{
return mul(ifa[i], mul
(fa[j], fa[i - j]));
}
}

//线性求逆元

vector<i64> get_inv(int k) 

{
vector<i64> in(k + 1, 1)
;
for (int i = 2
; i <= k; i++) {
in[i] =
mul(in[mod % i], sub
(mod, mod / i));
}
return
in;
}
}

using namespace
myMath;

vector<i64> ans;

void init(int t)
{
Comb::
init(t + 10
);
ans.
resize(t + 10
);
for (int i = 1
; i <= t; i++) {
ans[i +
1] = add(ans[i / 2 + 1
], i);
}
for (int i = 1
; i <= t; i++) {
ans[i] =
add(ans[i], ans[i - 1
]);
}
for (i64 i = 3
; i <= t; i++) {
ans[i] =
mul(ans[i], Comb::iC(i, 2
));
}
}

int main()
{
ios::
sync_with_stdio(0), cin.tie(0
);
init(1e6 + 100
);
int t = 0
;
cin >> t;
for (int i = 1
; i <= t; i++) {
int
x;
cin >> x;
cout << ans[x] <<
"\n"
;
}
}
