题目描述

Marin 想让你计算有多少个排列是美丽的。一个长度为 $n$ 的美丽排列是指满足以下性质的排列：

其中 $\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]$，但它不是美丽的，因为 $\gcd(1 \cdot 1) = 1$。

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

由 ChatGPT 4.1 翻译

样例

7
1
2
3
4
5
6
1000

0
1
0
4
0
36
665702330