建模与关键观察\n\n### 1）闭环 = 两个完美匹配的并\n\n把每个单元视为一个点：\n\n* “左侧随机配对”在这些点上给出一个完美匹配 $\sigma$（若干 2-环）；\n* “右侧随机配对”给出另一完美匹配 $\tau$。\n\n把两种边（左/右）一起看，就是一个每点度为 2、边颜色交替的图，因此一定是若干个偶长环的并。$X$ 就等于这些环的个数。\n\n等价地，固定其中一个匹配（例如把 $\sigma=(1\,2)(3\,4)\cdots(2n-1\,\,2n)$ 固定），只随机另一个匹配 $\tau$ 即可，分布不变。\n\n### 2）逐步暴露（经典“开链闭合”过程）\n\n从最小未访问的点出发，沿着“固定边 $\sigma$ 与当前已暴露的 $\tau$ 边”交替行走，会得到一条开链。当我们在这条链的“游离端”给它再连上一条新的 $\tau$ 边时：\n\n* 共有 $2k-1$ 个可选端点（当前游离端除外已占去 $2k-2$ 个），\n* 其中恰有 1 个会把开链闭成一个环，\n* 因而第 $k$ 次尝试“闭合”的概率为\n\n $p_k=\frac{1}{2k-1}.$\n\n把“在第 $k$ 次形成 $\tau$ 边时闭合一个环”的事件记为指示变量 $I_k$。整个构造会进行 $n$ 次，因此\n\n$X=\sum_{k=1}^{n} I_k.$\n\n进一步可以证明：这些 $I_k$ 彼此两两独立。理由：在第 $k$ 次时，游离端是均匀随机的，能闭合的那个端点在剩余的 $2k-1$ 个端点中是唯一且等可能的；第 $k$ 次是否闭合完全由本次选择决定，与之前是否闭合无关（之前只改变“剩余是谁”，不改变“唯一能闭合端点的相对概率”）。\n\n\n## 期望与方差的封闭式\n\n由线性期望：\n\n \n\n由两两独立：\n\n \n\n这正好与题面样例相符：\n$n=1$ 时 $E=1,\,D=0$；\n$n=2,3$ 时把上式转为模 $M$ 意义下的分数即可得到样例输出。\n\n## 模运算与实现要点\n\n* $M$ 为大质数，用费马小定理求逆元：$a^{-1}\equiv a^{M-2}\pmod M$。\n* \n* 多组数据，建议先把所有 $n$ 的最大值记为 $N$，预处理：\n\n * 线性求逆（$O(N)$）得到 $1,2,\dots,2N-1$ 的逆元；\n * 仅对奇数做两条前缀和：\n $S_1[k]=\sum_{i=1}^{k}(2i-1)^{-1},\quad$ $S_2[k]=\sum_{i=1}^{k}(2i-1)^{-2}$。\n * 单次回答：$(S_1[n]-S_2[n])\bmod M$。\n\n### 复杂度分析\n\n* 预处理时间 $O(N)$，空间 $O(N)$；\n* 单次询问 $O(1)$。\n 在约束 $T\le 10^4,\; n\le 10^6$ 下完全可行。\n\n\n## 代码\n\n### Python\n\npython\nimport sys\nfrom array import array\n\nMOD = 998244353\n\ndef read_ints():\n return list(map(int, sys.stdin.buffer.read().split()))\n\ndef solve():\n data = read_ints()\n it = iter(data)\n T = next(it)\n ns = [next(it) for _ in range(T)]\n N = max(ns)\n\n # 线性求逆：inv[i] = i^{-1} (mod MOD)，i=1..(2N-1)\n L = 2 * N - 1\n inv = array('i', [0]) * (L + 1)\n inv[1] = 1\n for i in range(2, L + 1):\n inv[i] = (MOD - (MOD // i) * inv[MOD % i] % MOD) % MOD\n\n # 只对奇数做前缀和\n S1 = [0] * (N + 1) # sum 1/(2i-1)\n S2 = [0] * (N + 1) # sum 1/(2i-1)^2\n for k in range(1, N + 1):\n j = 2 * k - 1\n x = inv[j]\n S1[k] = (S1[k - 1] + x) % MOD\n S2[k] = (S2[k - 1] + (x * x) % MOD) % MOD\n\n out = []\n for n in ns:\n ans = S1[n] - S2[n]\n if ans < 0:\n ans += MOD\n out.append(str(ans))\n sys.stdout.write("\n".join(out))\n\nif __name__ == "__main__":\n solve()\n\n\n### Java\n\njava\nimport java.io.*;\nimport java.util.*;\n\npublic class Main {\n static final int MOD = 998244353;\n\n public static void main(String[] args) throws Exception {\n Scanner sc = new Scanner(System.in);\n int T = sc.nextInt();\n int[] ns = new int[T];\n int N = 0;\n for (int i = 0; i < T; i++) {\n ns[i] = sc.nextInt();\n N = Math.max(N, ns[i]);\n }\n int L = 2 * N - 1;\n\n // 线性求逆 inv[i] = i^{-1} mod MOD\n int[] inv = new int[L + 1];\n inv[1] = 1;\n for (int i = 2; i <= L; i++) {\n long val = (MOD - (long)(MOD / i) * inv[MOD % i] % MOD) % MOD;\n inv[i] = (int) val;\n }\n\n // 前缀和（只对奇数）\n int[] s1 = new int[N + 1];\n int[] s2 = new int[N + 1];\n for (int k = 1; k <= N; k++) {\n int j = 2 * k - 1;\n long x = inv[j];\n s1[k] = (int) ((s1[k - 1] + x) % MOD);\n s2[k] = (int) ((s2[k - 1] + x * x) % MOD);\n }\n\n StringBuilder sb = new StringBuilder();\n for (int n : ns) {\n int ans = s1[n] - s2[n];\n if (ans < 0) ans += MOD;\n sb.append(ans).append('\n');\n }\n System.out.print(sb.toString());\n }\n}\n\n\n### C++\n\ncpp\n#include <bits/stdc++.h>\nusing namespace std;\nconst int MOD = 998244353;\n\nint addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }\nint submod(int a, int b){ a-=b; if(a<0) a+=MOD; return a; }\n\nint main(){\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n int T; \n if(!(cin >> T)) return 0;\n vector<int> ns(T);\n int N = 0;\n for(int i=0;i<T;i++){ cin >> ns[i]; N = max(N, ns[i]); }\n\n int L = 2*N - 1;\n\n // 线性求逆：inv[i] = i^{-1} (mod MOD)\n vector<int> inv(L+1);\n inv[1] = 1;\n for(int i=2;i<=L;i++){\n long long v = (MOD - 1LL*(MOD/i)*inv[MOD%i]%MOD) % MOD;\n inv[i] = (int)v;\n }\n\n // 只对奇数做前缀和\n vector<int> s1(N+1, 0), s2(N+1, 0);\n for(int k=1;k<=N;k++){\n int j = 2*k - 1;\n long long x = inv[j];\n s1[k] = addmod(s1[k-1], (int)x);\n s2[k] = addmod(s2[k-1], (int)(x*x%MOD));\n }\n\n for(int n: ns){\n int ans = submod(s1[n], s2[n]);\n cout << ans << '\n';\n }\n return 0;\n}\n