Consider the bubble sort algorithm:

for i = 1 to n do
    for j = 1 to n - 1 do
        if(p[j] > p[j + 1])
            swap(p[j], p[j+1])

Let denote $f(p)$ as the number of times the function $swap$ is called when we run the bubble sort algorithm on permutation $p$. We call $p$ a good permutation if $f(p)=\frac{1}{2}\sum _{i=1}^n|i-p_i|$. One can prove $\frac{1}{2}\sum _{i=1}^n|i-p_i|$ is a tight lower bound for permutations of length $n$.

You are given an permutation $q$ and asked to the number of good permutations of length $n$ that is strictly lexicographically larger than $q$. The output might be too large, so you only need to output the answer under modulo $998244353$

Input Specification

The first line contains an integer $T$, the number of test cases.

For each test case,

• The first line contains an integer $n$, which is the length of the permutation.
• The second lines contains $n$ integers in the permutation.

Output Specification

For each test case, output the answer under modulo $998244353$

Constraints

For all test file, $T=5$.

$n_{max}$ is the maximum $n$ in a single file. $\sum n$ is the sum of $n$ is a single file.

Sample 1 Input

1
3
1 3 2

Sample 1 Output

3

Sample 1 Explanation

All permutation lexicographically larger than "$132$" is good except "$321$"

Sample 2 Input

1
4
1 4 2 3

Sample 2 Output

9

Subtask

For all data, $T=5$ is satisfied (sample may not be satisfied).

Denote $n_{\max }$ to denote the maximum value of $n$ in each set of data, and $\sum n$ to denote the sum of $n$ for all data.

test point	$n_{\max }=$	$\sum n\le$	special properties
1	$8$	$5n_{\max }$	None
2	$9$	$5n_{\max }$	none
3	$10$	$5n_{\max }$	None
4	$12$	$5n_{\max }$	None
5	$13$	$5n_{\max }$	None
6	$14$	$5n_{\max }$	None
7	$16$	$5n_{\max }$	None
8	$16$	$5n_{\max }$	None
9	$17$	$5n_{\max }$	None
10	$18$	$5n_{\max }$	None
11	$18$	$5n_{\max }$	None
12	$122$	$700$	$\mathrm{\forall }i{q}_i=i$
13	$144$	$700$	None
14	$166$	$700$	None
14	$166$	$700$	None
16	$233$	$700$	None
17	$777$	$4000$	$\mathrm{\forall }i{q}_i=i$
18	$888$	$4000$	None
19	$933$	$4000$	None
20	$1000$	$4000$	None
21	$266666$	$2000000$	$\mathrm{\forall }i{q}_i=i$
22	$333333$	$2000000$	none
23	$444444$	$2000000$	None
24	$555555$	$2000000$	None
25	$600000$	$2000000$	none