Recently, Xiao S has developed a keen interest in bubble sort. To simplify the problem, Xiao S only studies bubble sort on permutations of $1$ to $n$.

The algorithm for bubble sort is described as follows:

Input: A permutation $p[1 \dots n]$ of length $n$. Output: The result of sorting $p$.

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

The number of swaps in bubble sort is defined as the number of times the swap operation is executed. It can be proven that a lower bound for the number of swaps is $\frac{1}{2} \sum_{i=1}^n |i - p_i|$, where $p_i$ is the number at the $i$-th position in the permutation $p$. If you are interested in the proof, you can refer to the Note.

Xiao S began to focus on studying permutations of length $n$ that satisfy the condition that the number of swaps equals $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ (hereafter, for convenience, we call all such permutations "good" permutations). He further wondered: are there many such permutations? Are they densely distributed?

Xiao S wants to calculate the number of "good" permutations that are strictly lexicographically greater than a given permutation $q$ of length $n$. However, he does not know how to do this and asks for your help. Considering that the answer might be very large, you only need to output the result modulo $998244353$.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $n$, where $n \le 6 \times 10^5$.

The next line contains $n$ positive integers, corresponding to $q_i$ in the problem description, ensuring the input is a permutation of $1$ to $n$.

Output

Output $T$ lines in total, each containing one integer. For each test case, output the number of "good" permutations strictly lexicographically greater than $q$, modulo $998244353$.

Examples

Input 1

1
3
1 3 2

Output 1

3

Note 1

Among the permutations lexicographically greater than $1\ 3\ 2$, all except $3\ 2\ 1$ are "good" permutations, so the answer is $3$.

Input 2

1
4
1 4 2 3

Output 2

9

Subtasks

The following table describes the input scale for each test case.

For all data, $T = 5$ is satisfied (the sample may not satisfy this). Let $n_{max}$ denote the maximum value of $n$ in each test case, and $\sum n$ denote the sum of $n$ over all test cases.

Note

The following is a proof that the lower bound for the number of swaps is $\frac{1}{2} \sum_{i=1}^n |i - p_i|$.

Sorting is essentially the movement of numbers, so the number of swaps in sorting should be describable by the total distance the numbers move. For the $i$-th position, assuming the number at this position in the initial permutation is $p_i$, we need to move this number to the $p_i$-th position, and the distance moved is $|i - p_i|$. Thus, the total distance moved is $\sum_{i=1}^n |i - p_i|$. Since bubble sort swaps two adjacent numbers at each step, and each swap can reduce the total distance moved by at most $2$, $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ is a lower bound for the number of swaps in bubble sort.

Not all permutations reach this lower bound. For example, when $n = 3$, consider the permutation $3\ 2\ 1$. The number of swaps after bubble sort is $3$, but $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ is only $2$.