Brandon likes sequences that go up and down. Given a list of $N$ integers, compute the number of subsequences that go up and down - that is to say, there is a unique maximal integer in the subsequence, and the prefix of the subsequence ending at that integer is strictly increasing, and the suffix of the subsequence starting at that integer is strictly decreasing. The subsequence must be nonempty.

Recall that a subsequence is obtained by deleting some (possibly zero) integers from the list. Two subsequences are distinct if and only if some integer is deleted in one subsequence but not the other.

Constraints

$1\le T\le {10}^6$

$1\le N\le {10}^6$

$1\le a_i\le N$

The sum of all $N$ in an input file will not exceed ${10}^6$.

Input Specification

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

$T$ test cases follow.

Each test case starts with a line containing a single positive integer, $N$. The next line contains $N$ space-separated positive integers.

Output Specification

Output $T$ lines. On the $i$th line, output the number of subsequences that go up and down, modulo $998244353$, for the $i$th test case.

Sample Input

2
3
1 3 2
4
1 3 2 4

Sample Output

7
13