409017: GYM103415 I Pudding Store

159 is a boy. He has a pudding store.

There are $$$n$$$ different puddings numbered from $$$1$$$ to $$$n$$$ lined up in a row in the pudding store. (Note that the $$$i$$$-th pudding in the row may not be the pudding with the number $$$i$$$.) Now, $$$n$$$ students numbered from $$$1$$$ to $$$n$$$ are coming to sample these puddings in a specific way. That is, for the $$$i$$$-th student, he will sample each one of the first $$$i$$$ puddings in the row. Sampling the pudding numbered $$$i$$$ gives the sampler a satisfaction value of $$$2\times i$$$. And if the sum of all satisfaction values that the $$$i$$$-th student gets is divisible by $$$i$$$, we would say that the $$$i$$$-th student is satisfied.

Now, 159 wants to know, how many different arrangements of the puddings in a row that every student will be satisfied after sampling. Two arrangements are different, if there exists a pudding that its position is different. Note that the number of arrangements may be very large so he just needs the remainder after division by $$$998244353$$$ of the result.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t \le 10$$$). Description of the test cases follows.

The first and only line of each test case contains one integer $$$n$$$ ($$$1\le n \le 10^9$$$) — the number of the puddings and the students.

For each test case, print a single line that contains one integer — the number of satisfying arrangements modulo $$$998244353$$$.

3
1
2
3

1
2
6