You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

假设游戏中有 $n$ 张牌（ $n$ 为偶数）。每张牌上都写有一个数字，介于 $1$ 和 $n$ 之间。卡片上的所有数字都是不同的。如果有 $x \gt y$ ，我们就说数字为 $x$ 的牌比数字为 $y$ 的牌强。

两个玩家Drb和Wfz玩这个游戏。一开始，他们每个人都得到了正好 $\frac{n}{2}$ 张牌，因此每张牌都属于一个玩家。然后，他们轮流先手。Drb的回合，然后是Wfz的回合，接着又是Drb，以此类推。

轮到一个玩家时，他必须出 $1$张他的牌。然后，如果对手没有比他出的牌更强的牌，对手就输了，游戏结束。否则，对手必须出一张更强的牌（也正好是一张牌）。这两张牌将从游戏中移除，回合结束。如果没有牌了，游戏就以平局结束；否则就轮到对手。

考虑在两名玩家之间分配牌的所有可能方法，以便他们每人都能得到正好一半的牌。你需要计算出：

• 使Wfz获胜的分配牌的方法数；

您可以假设两位玩家都以最佳方式出牌（即如果一位玩家无论对手如何出牌都能获胜，那么他就是赢家）。如果至少有一张牌在其中一种分配方式下给了Drb，而在另一种分配方式下给了Wfz，那么这两种分配牌的方式就是不同的，答案可能很大你需要对 $998244353$ 取模。

例如，假设 $n = 4$ ，Drb得到的牌是 $[2, 3]$ ，而Wfz得到的牌是 $[1, 4]$ 。那么棋局可能如下

• 如果Drb出牌 $2$ ，那么Wfz必须回应牌 $4$ 。然后，Drb的回合结束，Wfz的回合开始。Wfz只剩下一张牌，即 $1$ ；他下了这张牌，而Drb回应的牌是 $3$ 。因此，游戏以平局结束；
• 如果Drb下出 $3$ 这张牌，那么Wfz必须回应 $4$这张牌。然后，Drb的回合结束，Wfz的回合开始。Wfz只剩下一张牌，即 $1$ ；他下了这张牌，而Drb回应的牌是 $2$ 。因此，游戏以平局结束。

Input Format

第一行包含一个 $T$，表示共有 $T$ 组测试数据； 每组测试数据包含一行输入，每行给出一个 $n$ 表示牌的数量，保证 $n$ 是偶数。

Output Format

共 $T$ 行，每行一个数表示你得到的答案。

Sample

Input 1

5
2
4
6
8
60

Output 1

0
2
7
27
248150916

Hint

$1 \leqslant n \leqslant 10^{5}$

$1 \leqslant T \leqslant 10^3$

$1 \leqslant \Sigma n \leqslant 10^5$