MoonLight的冒泡排序难题
题号：NC252716
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Moonlight 最近迷上了冒泡排序。今天，他想动手试一试。

于是，氧气少年给了 MoonLight 一个长度为 n(1\leq n\leq 2\cdot 10^5) 的排列 p，好让他练练手。

MoonLight 会不停地进行下面的操作，直到当前排列变成严格递增的排列：
  • 选择一个最大的、不满足 p_i=i 的元素 p_i，然后将其向后移动到位置 p_i，其他元素保持原来的顺序不变。
上述过程可以用下面的伪代码表示：
\boxed<br />{<br /> \begin {split}<br /> & \mathbf{while}\ \ p\ \text{is not in increasing order}\ \ \mathbf{do}\\<br /> & \quad\quad pos\leftarrow \text{the index of the maximum }p_i\text{ that satisfies }p_i\neq i\\<br /> & \quad\quad val\leftarrow \text{the value of the maximum }p_i\text{ that satisfies }p_i\neq i\\<br /> & \quad\quad \mathbf{for}\ \ i\ \ \text{from}\ \ pos\ \ \text{to}\ \ val-1\ \ \mathbf{do} \\<br /> & \quad \quad \quad\quad \text{Swap}\ \ p_i\ \text{with}\ p_{i+1} \\<br /> & \quad\quad\mathbf{end\ for} \\<br /> & \mathbf{end\ while} \\<br /> \end {split}<br />}

现在，氧气少年不小心打乱了这个排列，每种排列出现的概率均等。

MoonLight 想知道，操作进行的轮数（也就是伪代码中 \text{while} 循环进行的轮数）的期望值。

可以证明，答案可以表示成 \frac{p}{q} 的形式。其中，p\geq 0,q\geq 1,\gcd(p,q)=1,q\mod 998244353\neq 0。因此你只需输出 p\cdot q^{998244351}\mod 998244353 即可。

输入描述:

第一行包含一个整数 T(1\leq T\leq 2\cdot 10^5)，表示测试用例的组数。

对于每组测试用例：

仅输入一行，包含一个整数 n(1\leq n\leq 2\cdot 10^5)，表示排列 p 的长度。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。
示例1

输入

复制 
3
1
2
3

输出

复制 
0
499122177
166374060

说明

对于第一组测试用例：

当 n=1 时，排列 p 只有一种可能：[1]，操作进行的轮数只可能是 0。

对于第二组测试用例：

当 n=2 时，排列 p 有两种可能：[1,2]\ [2,1]，这两种情况出现的概率均为 \frac{1}{2}，操作进行的轮数分别是 0,1。期望为 \frac{1}{2}\cdot 0+\frac{1}{2}\cdot 1=\frac{1}{2}。1\cdot 2^{998244351} \mod 998244353=499122177。