Doctor Sunset is doing a survey about global warming. He selected two cities $A$ and $B$, and has gathered the average air temperature of these two cities throughout passed $n$ days. On the $i$-th day, the average air temperature of $A$ was $a_i$ while the average air temperature of $B$ was $b_i$.
Doctor Sunset drew a key graph using the temperature data. From his observation, there are several facts about the data:
Unfortunately, Doctor Sunset erased all the data of city $B$ by mistake just now. But he can recover the array $b$ by the facts described above. Please write a program to help Sunset count the number of possible arrays that can be $b$.
The first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.
In each test case, there is one integer $n (1 <= n <= 2 times 10^5)$ in the first line, denoting the number of days.
In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= n)$, denoting the average air temperature of city $A$. The input is always valid, so you can assume $a_1 <= a_2 <= a_3 <= \\dots <= a_n$.
It is guaranteed that $sum n <= 5 times 10^5$.
For each test case, print a single line containing an integer, denoting the number of possible arrays that can be $b$. As the answer can be very large, output it modulo $998244353$.
## Input
The first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 2 times 10^5)$ in the first line, denoting the number of days.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= n)$, denoting the average air temperature of city $A$. The input is always valid, so you can assume $a_1 <= a_2 <= a_3 <= \\dots <= a_n$.It is guaranteed that $sum n <= 5 times 10^5$.
## Output
For each test case, print a single line containing an integer, denoting the number of possible arrays that can be $b$. As the answer can be very large, output it modulo $998244353$.
[samples]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 50 $.
Let $ S_n $ be the set of all permutations of $ \{1, 2, \dots, n\} $.
A permutation $ \pi \in S_n $ is *almost sorted* if $ \mathrm{LIS}(\pi) \geq n - 1 $, where $ \mathrm{LIS}(\pi) $ denotes the length of the longest increasing subsequence of $ \pi $.
Let $ B^k(\pi) $ denote the permutation obtained after applying $ k $ passes of bubble sort to $ \pi $.
**Constraints**
1. $ 1 \leq n, k \leq 50 $
2. $ q $ is a prime number with $ 10^8 \leq q \leq 10^9 $
3. Number of test cases $ T \leq 5000 $
**Objective**
For each test case, compute:
$$
\left| \left\{ \pi \in S_n \mid \mathrm{LIS}(B^k(\pi)) \geq n - 1 \right\} \right| \mod q
$$