时空限制

1S/512M

题目描述

apiadu 正在为一场算法竞赛招募出题组。现有 $n$ 位报名者，apiadu 需要将他们全部分配到若干个出题组中。根据规定，一个出题组的构成必须满足以下所有条件：

1. 每个出题组必须包含恰好一名出题人和若干名验题人。
2. 每个出题组的总人数必须在 $2$ 到 $5$ 人内（即 $1$ 个出题人配上 $1 \sim 4$ 个验题人）。
3. $n$ 位报名者中的每一个人都必须被分配到恰好一个出题组中。

两个分组方案被认为是不同的，当且仅当：

• 存在一个人，在两种方案中属于不同的出题组。
• 或者，存在一个出题组，其成员构成完全相同，但在两种方案中指定的出题人不同。

现在，apiadu 想知道对于给定的 $n$，总共有多少种有效的分组方案。由于方案数可能非常大，请将结果对 $998244353$ 取模。

格式

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行包含一个正整数 $n$，代表报名者的总人数。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示将 $n$ 个人分组的总方案数，结果对 $998244353$ 取模。

样例

样例输入 #1

3
4
3
1000

样例输出 #1

16
3
178726897

样例解释 #1

对于 $n=4$ 的情况：

假设四个人分别为 $1,2,3,4$。有两种分组的方式：

• 方式一：所有 $4$ 个人组成一个大组。
  • 这个组的成员是 $\{1,2, 3,4\}$，任何人都可以成为出题人。因此有 $4$ 种方案。
• 方式二：$4$ 个人分成两个两人组。
  • 划分成员的方式有 3 种：$(\{1, 2\}, \{3, 4\}), (\{1, 3\}, \{2, 4\}), (\{1, 4\}, \{2, 3\})$。
  • 对于每一种划分方式，第一个组有 $2$ 种出题人选择，第二个组也有 $2$ 种出题人选择，共 $2 \times 2 = 4$ 种方案。
  • 因此方式二共有 $3 \times 4 = 12$ 种方案。

总方案数为 $4 + 12 = 16$ 种。

对于 $n=3$ 的情况：

只能将 $3$ 个人分到同一个组。组内 $3$ 人都可以担任出题人，因此有 $3$ 种方案。

数据规模

对于 $20\%$ 的数据，$1 \leq T \leq 3$，$2 \leq n \leq 10$。

对于 $40\%$ 的数据，$1\leq T \leq 10$， $2 \leq n \leq 100$。

对于 $100\%$ 的数据，保证 $1 \leq T \leq 10^5$，$2 \leq n \leq 10^6$。