活动
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小Z和他的朋友们一起外出参加活动。到达目的地后，大家决定玩游戏。作为活动的发起者，小Z准备了三种游戏：斗兽棋、斗地主和麻将。每种游戏都有不同的参与人数要求：

  •  斗兽棋需要 2 人一组。
  •  斗地主需要 3 人一组。
  • 麻将需要 4 人一组。
为了保证没有人落单，小Z希望每个人都能参与其中的某一个游戏，且每个人只能参加一个游戏。现在，小Z想知道，对于给定的人数 n，有多少种不同的方式可以将所有人分组，参加这些游戏。两种分组方式被认为是不同的，当且仅当存在某一个人在两种分组方式中与其玩游戏的人不同。具体细节可以参考样例解释。

由于可能的分组方式非常多，结果需要对 998244353 取模。

输入描述:

本题包含多组测试数据。

第一行给出一个整数 T \; (1 \leq T \leq 10^5)，表示测试数据的组数。

接下来有 T 行,每行给出一个正整数 n \; (1 \leq n \leq 10^6)，表示人数。

输出描述:

输出 T 行，每行 1 个整数，其中第 i 行数表示第 i 个数据的答案。
示例1

输入

复制 
7
1
2
3
4
5
6
7

输出

复制 
0
1
1
4
10
40
140

说明

n = 4 时有 4 种情况，他们分别是：
1. 4 个人一起打麻将。
2. 1 号和 2 号一起玩斗兽棋，3 号和 4 号一起玩斗兽棋。
3. 1 号和 3 号一起玩斗兽棋，2 号和 4 号一起玩斗兽棋。
4. 1 号和 4 号一起玩斗兽棋，2 号和 3 号一起玩斗兽棋。