← 返回题目列表

Codeforces · 1658/B

B. Marin 和反互质排列

中文机器翻译题面 查看原题

Marin 希望你计算出美丽的排列数量。长度 $$$n$$$ 的美丽排列是具有以下属性的排列: $$$$$$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$$$$$ 其中 $$$\gcd$$$ 是最大公约数。

排列是一个数组,由 $$$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

7
1
2
3
4
5
6
1000

输出 #1

0
1
0
4
0
36
665702330

注意

在第一个测试用例中,我们只有一个排列,即 $$$[1]$$$ 但它并不漂亮,因为 $$$\gcd(1 \cdot 1) = 1$$$。

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