建模与关键观察

1）闭环 = 两个完美匹配的并

把每个仪器视为一个点：

• “左侧随机配对”在这些点上给出一个完美匹配 $\sigma$（若干 2-环）；
• “右侧随机配对”给出另一完美匹配 $\tau$。

把两种边（左/右）一起看，就是一个每点度为 2、边颜色交替的图，因此一定是若干个偶长环的并。每个环需要 1 个信号源，所以

题目内容

如下图所示，有 $2×n$ 个仪器，中间的方块是仪器的主体，每个仪器可以充当接收器或者信号源；主体的左右两侧是两个接线点。

现在，我们将左端 $2×n$ 个接线点随机分成 $n$ 组，每组各含两个点，并将右端 $2×n$ 个接线点同样随机分成 $n$ 组。然后将每组的两个接线点用导线连接。

这样一来，我们就得到了一组封闭的信号线路。具体而言：

• 信号从任一信号源 $i$ 出发，通过右侧接线点；

• 随后，信号通过与右侧接线点连接的导线到达另外一个仪器的左侧接线点，再经过仪器主体到达右侧接线点；此时，如果这个仪器是接收器，那么就视为接收到了信号(注意，接收到信号不会影响信号继续往后传递)。

这个过程持续进行，最终会形成若干个独立的循环。

现在，记 $x$ 表示在所有接收器均能接收到信号的前提下， $2×n$ 个仪器中作为信号源的最少数量。求解 $x$ 的方差。

可以证明答案可以表示为一个不可约分数 $\frac {p}{q}$，为了避免精度问题，请直接输出整数 $(p×q^{-1}$ $mod$ $M)$ 作为答案，其中 $M=998$ $244$ $353$ ，$q^{-1}$ 是满足 $q×q^{-1}≡1(mod$ $M)$ 的整数。更具体地，你需要找到一个整数 $x ∈ [0,M)$ 满足 $x × q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。

【提示】 本题中，如果您需要使用到除法的取模，即计算 $(p×q^{-1}$ $mod$ $M)$时，$q^{-1}$ 需要使用公式 $(q^{M-2}$ $mod$ $M)$ 得到。例如，计算 $(\frac {5}{4}$ $mod$ $M)$：

$\frac {4^{-1}}{(\frac {5}{4} mod M) }$

$4^{-1}=(4^{M-2}$ $mod$ $M$) $=748683265$

$(\frac {5}{4}$ $mod$ $M)= 5×4^{-1}$ $mod$ $M$ $=5×748$ $683$ $265$ $mod$ $M$ $=748$ $683$ $266$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤ T < 10^4)$ 代表数据组数，每组测试数据描述如下：

在一行上输入一个整数 $n(1 ≤n≤ 10^6)$ 代表仪器的数量。

输出描述

对于每组测试数据，新起一行输出一个整数，表示 $x$ 的方差对 $M =998$ $244$ $353$ 取模后的结果。

样例1

输入

3
1
2
3

输出

0
887328314
168592380

说明

对于第一组测试数据，左、右两侧各仅有一种配对方式，构成一个长度为 $2$ 的循环。最小信号源数为 $1$ ，如下图所示。因此 $E(X)=1，D(X)=0$ 。

对于第二组测试数据，左侧有三种配对 ({$1,2$},{$3,4$};{$1,3$},{$2,4$};{$1,4$},{$2,3$})，右侧同样三种，合计 $3×3=9$ 种等可能组合。计算可得，需要 $1$ 个信号源的概率为 $\frac {6}{9}$ (如下左图所示，为其中一种情况)，需要 $2$ 个信号源的概率为$\frac {3}{9}$ (如下右图所示，为其中一种情况)，故 :

• $E(X)=1×\frac {2}{3}+2×\frac {1}{3}=\frac {4}{3}$
• $D(X)=E([X-E(X)]^2)=$$(1-\frac {4}{3})^2×\frac {2}{3}$$+(2-\frac {4}{3})^2$$×\frac {1}{3}$$=\frac {2}{9}$ 。

我们能够找到， $887$ $328$ $314$ $×9=7$ $985$ $954$ $826$ 对 $M$ 取模后恰好等于分子 $2$，所以 $887$ $328$ $314$ 是需要输出的答案。