F. Non Unique
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. Let $$$f(a, i)$$$ denote the number of indices $$$j$$$ such that $$$1 \le j \lt i$$$ and $$$a_j \gt a_i$$$. Let $$$F(a)$$$ be the set of indices $$$i$$$ having the maximum value of $$$f(a, i)$$$.

You do not want $$$F(a)$$$ to consist of only one element, so you may perform the following operation any number of times:

  • Select $$$1 \le i \lt n$$$, and swap $$$a_i$$$ and $$$a_{i + 1}$$$.

Let $$$x$$$ be the minimum number of operations needed so that $$$|F(a)| \ge 2$$$. It can be proven that $$$x$$$ is finite.

Find the number of ways to achieve $$$|F(a)| \ge 2$$$ in exactly $$$x$$$ operations.

Since the number might be large, output it modulo $$$998\,244\,353$$$.

Two ways are different if there exists an index $$$j$$$ such that the indices selected in the $$$j$$$-th operation are different.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains a positive integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print the number of ways modulo $$$998\,244\,353$$$.

Example
Input
3
2
1 1
3
1 2 1
3
2 3 1
Output
1
2
2
Note

In the first test case, we do not need to perform any operation. So, the number of ways is $$$1$$$.

In the second test case, we can get $$$|F(a)| \ge 2$$$ by performing $$$1$$$ operation. There are $$$2$$$ ways: we can select $$$i = 1$$$ or $$$i = 2$$$.

In the third test case, we can achieve $$$|F(a)| \ge 2$$$ by performing $$$2$$$ operations. There are $$$2$$$ ways:

  • Select $$$i = 1$$$ in the first operation and $$$i = 2$$$ in the second operation. Then we get $$$a = [3, 1, 2]$$$ and $$$F(a) = [2, 3]$$$.
  • Select $$$i = 2$$$ in the first operation and $$$i = 1$$$ in the second operation. Then we get $$$a = [1, 2, 3]$$$ and $$$F(a) = [1, 2, 3]$$$.