CF1658B.Marin and Anti-coprime Permutation

Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length $n$ is a permutation that has the following property: $$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) \gt 1, $$ where $\gcd$ is the greatest common divisor.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

马林希望你计算有多少个“优美”排列。一个长度为 $n$ 的优美排列是指满足如下性质的排列：

$$\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1,$$

其中 $\gcd$ 表示最大公约数。

排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数组成的、顺序任意的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中却出现了 $4$）。

The first line contains one integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^3$).

第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试用例的数量。

每个测试用例由一行组成，该行包含一个整数 $n$（$1 \le n \le 10^3$）。

For each test case, print one integer — number of beautiful permutations. Because the answer can be very big, please print the answer modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——优美排列的数量。由于答案可能非常大，请将答案对 $998\,244\,353$ 取模后输出。

In first test case, we only have one permutation which is $[1]$ but it is not beautiful because $\gcd(1 \cdot 1) = 1$.

In second test case, we only have one beautiful permutation which is $[2, 1]$ because $\gcd(1 \cdot 2, 2 \cdot 1) = 2$.

在第一个测试用例中，我们只有一个排列 $[1]$，但它不是优美的，因为 $\gcd(1 \cdot 1) = 1$。

在第二个测试用例中，我们只有一个优美的排列 $[2, 1]$，因为 $\gcd(1 \cdot 2, 2 \cdot 1) = 2$。