I. Temperature Survey
time limit per test
8 с
memory limit per test
512 megabytes
input
standard input
output
standard output

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:

  • All the values are integers within $$$[1,n]$$$.
  • Global warming is ture, so the temperature is non-decreasing, which means $$$a_1\leq a_2\leq a_3\leq\dots\leq a_n$$$ and $$$b_1\leq b_2\leq b_3\leq\dots\leq b_n$$$.
  • City $$$B$$$ is always not hotter than $$$A$$$, which means $$$b_i\leq a_i$$$ for all $$$i\in[1,n]$$$.

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$$$.

Input

The first line of the input contains an integer $$$T(1\leq T\leq 100)$$$, denoting the number of test cases.

In each test case, there is one integer $$$n(1\leq n\leq 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\leq a_i\leq n)$$$, denoting the average air temperature of city $$$A$$$. The input is always valid, so you can assume $$$a_1\leq a_2\leq a_3\leq\dots\leq a_n$$$.

It is guaranteed that $$$\sum n\leq 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$$$.

Example
Input
3
4
1 1 1 1
4
1 2 3 4
4
4 4 4 4
Output
1
14
35