CF1658B Marin and Anti-coprime Permutation

Marin 想让你计算有多少个排列是美丽的。一个长度为 $n$ 的美丽排列是指满足以下性质的排列： $$ \gcd (1 \cdot p_1,\, 2 \cdot p_2,\, \dots,\, n \cdot p_n) > 1, $$ 其中 $\gcd$ 表示[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 排列是指由 $n$ 个 $1$ 到 $n$ 的不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。

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

对于每个测试用例，输出一个整数，表示美丽排列的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，只有一个排列 $[1]$，但它不是美丽的，因为 $\gcd(1 \cdot 1) = 1$。 在第二个测试用例中，只有一个美丽排列 $[2, 1]$，因为 $\gcd(1 \cdot 2, 2 \cdot 1) = 2$。 由 ChatGPT 4.1 翻译