Notice：Don't output extra spaces at the end of one line.
Koishi loves counting problems.
There are two permutations P1,P2. 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 P1,P2, 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 P1 and P2 arbitrarily. Given n，How many different A can be generated? modulo 998244353
输入格式
The first line contains an positive integer T(1≤T≤105). There are T test cases. The following T lines, each contains an positive integer n(1≤n≤105).
输出格式
You should output T lines, each contain a non-negative integer integer representing the answer