159 是一个男孩子。他有一家布丁店。

布丁店里有 $n$ 个不同的布丁，编号为 $1$ 到 $n$，它们排成一排。（注意，排在第 $i$ 个位置的布丁的编号不一定是 $i$。）现在，有 $n$ 个编号为 $1$ 到 $n$ 的学生将以一种特定的方式来品尝这些布丁。具体来说，对于第 $i$ 个学生，他会品尝排在队伍前 $i$ 个位置的每一个布丁。品尝编号为 $i$ 的布丁会给品尝者带来 $2 \times i$ 的满意度。如果第 $i$ 个学生获得的所有满意度之和能被 $i$ 整除，我们就说第 $i$ 个学生是满意的。

现在，159 想知道，有多少种不同的布丁排列方式，使得每个学生在品尝后都能感到满意。如果存在一个布丁在两种排列中的位置不同，则认为这两种排列是不同的。注意，排列的数量可能非常大，因此他只需要输出结果模 $998244353$ 的余数。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10$)。接下来是测试用例的描述。

每个测试用例的第一行也是唯一的一行包含一个整数 $n$ ($1 \le n \le 10^9$) —— 布丁和学生的数量。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 满足条件的排列数量模 $998244353$ 的值。

样例

输入样例 1

3
1
2
3

输出样例 1

1
2
6