C

题目描述

给定 $n$ ，求所有长度为 $n$ 的错排的逆序对数之和。

一个长度为 $n$ 的排列 $p$ 是错排当且仅当满足对于所有 $i$ ,$p_i\neq i$ 。

一个排列 $p$ 的逆序对数定义为 $\sum\limits_{1\leq i< j\leq n}[p_i>p_j]$ 。

一个测试点含有多组数据。

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $T$ ，表示测试组数。

接下来 $T$ 行每行一个整数 $n$ 。

输出格式

$T$ 行，每行一个整数表示这组数据的答案。

输入样例

3
2
3
114514

输出样例

1
4
556483447

样例解释

对于 $n=2$ ，仅有一个错排 $[2,1]$ ，一个逆序对。

对于 $n=3$ ，有两个错排 $[3,1,2],[2,3,1]$ ，均有两个逆序对，共 $4$ 个。

数据范围

对于 $10\%$ 的数据 ，满足 $n\leq 10$ 。

对于 $20\%$ 的数据 ，满足 $n\leq 20$ 。

对于 $40\%$ 的数据 ，满足 $n\leq 100$ 。

对于 $60\%$ 的数据 ，满足 $n\leq 5000$ 。

对于 $80\%$ 的数据 ，满足 $n\leq 200000$ 。

对于 $100\%$ 的数据 ，满足 $n\leq 10^7$ 。

对于所有数据，满足 $T\leq 200000$ 。