最近，小 S 对冒泡排序产生了浓厚的兴趣。为了问题简单，小 S 只研究对 1 到. n 的排列的冒泡排序。 

下面是对冒泡排序的算法描述。

输入：一个长度为 n 的排列 p[1...n] 输出：p 排序后的结果。

 for i = 1 to n do 

     for j = 1 to n - 1 do 

         if(p[i] > p[i + 1])  交换 p[i] 与 p[i + 1] 的值 

冒泡排序的交换次数被定义为交换过程的执行次数。

可以证明交换次数的一个下界是 ，其中 pi 是排列 p 中第 i 个位置的数字。如果你对证明感兴趣，可以看提示。 

小 S 开始专注于研究长度为 n 的排列中，满足交换次数 = ， 的排列 （在后文中，为了方便，我们把所有这样的排列叫“好”的排列）。

他进一步想，这样的 排列到底多不多？它们分布的密不密集？ 

小 S 想要对于一个给定的长度为 n 的排列 q，计算字典序严格大于 q 的“好”的 排列个数。

但是他不会做，于是求助于你，希望你帮他解决这个问题，考虑到答案可能会很大，因此只需输出答案对 998244353 取模的结果。 

输入描述:

输入第一行包含一个正整数 T，表示数据组数。 
对于每组数据，第一行有一个正整数 n, 保证 n ≤ 6 × 105。 
接下来一行会输入 n 个正整数，对应于题目描述中的 qi，保证输入的是一个 1 到n 的排列。 

输出描述:

输出共 T 行，每行一个整数。

对于每组数据，输出一个整数，表示字典序严格大于 q 的“好”的排列个数对
998244353 取模的结果。

1
3
1 3 2

3

字典序比 1 3 2 大的排列中，除了 3 2 1 以外都是“好”的排列，故答案为 3

1
4
1 4 2 3

9

备注:

下面是对本题每个测试点的输入规模的说明。 
对于所有数据，均满足 T = 5 (样例可能不满足).记 nmax 表示每组数据中 n 的最大值，
∑n 表示所有数据的 n 的和。

下面是对交换次数下界是的证明。 
排序本质上就是数字的移动，因此排序的交换次数应当可以用数字移动的总距离来描述。
对于第 i 个位置，假设在初始排列中，这个位置上的数字是 pi，那么我们需要将这个数字移动到第 pi 个位置上，移动的距离是 |i − pi|。
从而移动的总距离就是 ，而冒泡排序每次会交换两个相邻的数字，每次交换可以使移动的总距离至多减少 2。
因此  是冒泡排序的交换次数的下界。并不是所有的排列都达到了下界，比如在 n = 3 的时候，考虑排列 3 2 1, 这个排列进行冒泡排序以后的交换次数是 3，但是只有 2。