骰子

Problem Description

假设扔骰子后每个面朝上的概率相同。那么对于扔两个骰子，会有 $\frac{1}{36}$ 的概率点数之和为 $2$，有 $\frac{2}{36}$ 的概率点数之和为 $3$ ... 以此类推，可以得到分布列：

现在 Cuking 发现，如果给这两个骰子重新标号，也可能得到相同的概率分布：例如第一个骰子六个面的点数为 $[1, 2, 2, 3, 3, 4]$，而第二个骰子六个面的点数为 $[1, 3, 4, 5, 6, 8]$。

现在 Cuking 在 Cuking-Yoshinow Space 中获得了两个标准的正 $n$ 面体骰子（具体地，标准正 $n$ 面体骰子的各个面依次标上了 $1, 2, \cdots, n$），这对标准骰子掷出的点数之和，可以得到类似的概率分布列：

现在 Cuking 想要知道有多少种方案，给两个正 $n$ 面体骰子 $A, B$ 的每个面分配正整数（不要求点数不同，也不要求不超过 $n$），使得掷出的点数之和与两个标准骰子掷出的点数之和得到的分布列相同。答案对 $998244353$ 取模。

注意：骰子 $A, B$ 是有序的。称两个分配方案不同，当且仅当两个方案中，某个骰子中某个点数在两个方案中的出现次数不同（即不需要考虑具体把每个点数分配到哪个面上）。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 20)$，表示数据组数。对于每组测试数据： 一行一个正整数 $n(1 \leq n < 120)$，表示骰子的面数。

Output

对于每组测试数据：输出一行一个整数，表示答案对 $998244353$ 取模后的值。

Sample Input

4
1
2
3
4

Sample Output

1
1
1
3

Hint

当 $n = 1, 2, 3$ 时，唯一一种合法的分配方案即为标准骰子。 当 $n = 4$ 时，有三种合法的分配方案：

• $A = [1, 2, 2, 3], B = [1, 3, 3, 5]$。
• $A = [1, 2, 3, 4], B = [1, 2, 3, 4]$，即为标准骰子。
• $A = [1, 3, 3, 5], B = [1, 2, 2, 3]$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）