ursul

"A da palma cu ursul"

Andrei a rezolvat problema excursie și după s-a gândit să meargă în excursie în pădure. Când s-a întors, la ieșirea din pădure era un urs. Ursul i-a pus $T$ întrebări de forma: „Îți dau un număr natural $N$. Spune cât este $C_N^0 \cdot (N + 0) + C_N^1 \cdot (N + 1) + C_N^2 \cdot (N + 2) + \dots + C_N^N \cdot (N + N)$.” Prin $C_N^K$ am notat combinări de $N$ luate câte $K$.
Andrei nu știe să rezolve problema, așa că te roagă pe tine să o rezolvi.

Cerință

Pentru fiecare număr $N$ dintre cele $T$ date de urs, tu trebuie să spui cât este $C_N^0 \cdot (N + 0) + C_N^1 \cdot (N + 1) + C_N^2 \cdot (N + 2) + \dots + C_N^N \cdot (N + N)$, mai formal $\sum_{i=0}^{N} C_N^i \cdot (N + i)$. Deoarece aceste numere pot fi foarte mari, va trebui să le afișezi modulo $998 \ 244 \ 353$.

Date de intrare

Pe prima linie se va afla numărul $T$. Apoi, pentru $i$ de la $1$ la $T$, pe linia $i + 1$, se va afla un număr $N$, reprezentând numărul dat de urs pentru a $i$-a întrebare.

Date de ieșire

Pe linia $i$ se va afla un singur număr reprezentând răspunsul la întrebarea $i$ a ursului, modulo $998 \ 244 \ 353$.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N \leq 10 ^ {18}$

Exemplul

stdin

4
2 
6
2344
5459875

stdout

12
576
47421958
201586235

Explicație

Pentru primul test, $C_2^0 \cdot (2 + 0) + C_2^1 \cdot (2 + 1) + C_2^2 \cdot (2 + 2) =$ $1 \cdot 2 + 2 \cdot 3 + 1 \cdot 4 = 2 + 6 + 4 = 12$, iar $12 \text{ mod } 998 \ 244 \ 353 = 12$, deci răspunsul este $12$.

Pentru al doilea test, $C_6^0 \cdot (6 + 0) + C_6^1 \cdot (6 + 1) + C_6^2 \cdot (6 + 2)$ $+ C_6^3 \cdot (6 + 3) + C_6^4 \cdot (6 + 4) + C_6^5 \cdot (6 + 5)$ $+ C_6^6 \cdot (6 + 6) = 1 \cdot 6 + 6 \cdot 7$ $+ 15 \cdot 8 + 20 \cdot 9 + 15 \cdot 10 + 6 \cdot 11$ $+ 1 \cdot 12 = 6 + 42 + 120 + 180 + 150 + 66 + 12 = 576$, iar $576 \text{ mod } 998 \ 244 \ 353 = 576$, deci răspunsul este $576$.