B. Maximum Combo
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a game where you have $$$n$$$ portals.

  1. Each Portal is labelled from $$$1$$$ to $$$n$$$
  2. You are Starting on Portal $$$1$$$
  3. If you are currently on Portal $$$i$$$, you can jump on Portal $$$j$$$ only if $$$j$$$ > $$$i$$$
  4. You will receive $$$i * j$$$ points for jumping from Portal $$$i$$$ to Portal $$$j$$$

You want to find that for a given $$$n$$$, what is the maximum points you can recieve if you jump optimally.

Since this score might be very large, find the answer modulo $$$998244353$$$

Input
  1. First line consists of a single integer $$$t$$$, number of testcases $$$(1 \leq t \leq 10^4)$$$
  2. For each test, a single integer is present $$$n$$$, the number of portals $$$(1 \leq n \leq 10^6)$$$
Output

Each test consists of a single integer as output, the maximum points

Example
Input
10
1
2
3
4
5
6
7
8
9
10
Output
0
2
3
10
10
21
21
42
42
55