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.