Counting

Problem Description

Notice：Don't output extra spaces at the end of one line. Koishi loves counting problems. There are two permutations $P_1,P_2$. Each permutation consists of $n$ integers from $1$ to $n$. Koishi wants to merge them. She has an array $A$. Initially $A$ is empty. In each operation, Koishi will compare two head elements of $P_1,P_2$, select the smaller one, erase it from the permutation and append it to $A$, if the two head elements are the same, Koishi can select one of them arbitrarily, and if one of permutation is already empty, Koishi will select the head element from the other one. Koishi will do this operation repeatedly until the two permutations are all empty. What's more, Koishi can also select $P_1$ and $P_2$ arbitrarily. Given $n$，How many different $A$ can be generated? modulo $998244353$

Input

The first line contains an positive integer $T(1\leq T\leq 10^5)$. There are $T$ test cases. The following $T$ lines, each contains an positive integer $n(1\leq n\leq 10^5)$.

Output

You should output $T$ lines, each contain a non-negative integer integer representing the answer

Sample Input

4
1
2
3
4

Sample Output

1
4
38
650

Source

2020 Multi-University Training Contest 7