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 "~1\text{ }3\text{ }2~" is good except "~3\text{ }2\text{ }1~"

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_\mathrm{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_\mathrm{max} =~	~\sum n \leq~	special properties
1	~8~	~5 \ n_\mathrm{max}~	None
2	~9~	~5 \ n_\mathrm{max}~	none
3	~10~	~5 \ n_\mathrm{max}~	None
4	~12~	~5 \ n_\mathrm{max}~	None
5	~13~	~5 \ n_\mathrm{max}~	None
6	~14~	~5 \ n_\mathrm{max}~	None
7	~16~	~5 \ n_\mathrm{max}~	None
8	~16~	~5 \ n_\mathrm{max}~	None
9	~17~	~5 \ n_\mathrm{max}~	None
10	~18~	~5 \ n_\mathrm{max}~	None
11	~18~	~5 \ n_\mathrm{max}~	None
12	~122~	~700~	~\forall i \enspace q_i = i~
13	~144~	~700~	None
14	~166~	~700~	None
14	~166~	~700~	None
16	~233~	~700~	None
17	~777~	~4000~	~\forall i \enspace q_i = i~
18	~888~	~4000~	None
19	~933~	~4000~	None
20	~1000~	~4000~	None
21	~266666~	~2000000~	~\forall i \enspace q_i = i~
22	~333333~	~2000000~	none
23	~444444~	~2000000~	None
24	~555555~	~2000000~	None
25	~600000~	~2000000~	none