D. Mira与古代密文

Mira 在古代地下都市第六层的墙面上发现了一些端倪，在这个全部都由合金打造的都市中，有一个特殊的地方使用了不同的材质。

Mira 决定探索一下暗门后面的秘密，于是她呼唤出精灵王这个智囊，请他帮忙将这个奇怪的材质转化成可以通过的物质。

这个奇怪的材质内暗藏着一个长度为 n 的数列 a，这个数列决定着分析这个材质的复杂程度。具体来说，你可以用数列 a 生成一个 1 ~ n 的排列 b，需要满足是的倍数。定义一个排列的权值为。

生成的排列 b 可以划分为两种：含有偶数个逆序对和含有奇数个逆序对的。这两种排列包含两种截然不同的力量，只有知道两种力量的总和之差，才能够分析出这个材质的内部构造。也就是要求出 所有含有偶数个逆序对的排列的权值总和，减去所有含有奇数个逆序对的排列的权值总和。

眼看精灵王没个半小时解决不了，Mira 想要求助于你，你能够帮她解决这个问题吗？

第一行一个正整数 T 表示需要解析的迷之材质个数。

下面 T 组描述，每组第一行一个整数 n。

第二行 n 个整数，第 i 个数表示。

输出 T 行，每行一个整数表示答案。这个答案可能会很大，你只需要输出它对 998244353 取模后的结果即可。

样例输入 #1

1
3
2 1 3

样例输出 #1

998244352

样例输入 #2

1
3
2 1 1

样例输出 #2

0

样例解释1

每个排列的权值为：

只有一种排列符合条件：b = {2, 1, 3}，逆序对数为 1。所以答案为：0×1−1×1=−1，对 998244353 取模后的结果为：998244352。

样例解释2

每个排列的权值为：

符合条件的序列有：

b = {2, 1, 3}，逆序对数为 1；

b = {2, 3, 1}，逆序对数为 2；

所以答案为：1×3−1×3=0。

对于 10% 的数据，有 n≤10。

对于 40% 的数据，有 n≤200。

对于另外 20% 的数据，保证 a 是一个 1∼n 的排列。

对于 100% 的数据，有。