During an expedition, Little H discovered an ancient seal. The seal is a sequence $A = [a_1, a_2, \dots, a_n]$ of length $n$. Initially, each element is a positive integer between $1$ and $m$.

Let $|A|$ denote the length of sequence $A$. Little H can perform the following modifications on the sequence:

1. Choose a strictly prefix-maximum element $a_s$ of sequence $A$, i.e., choose $1 \le s \le |A|$ such that $\forall 1 \le j < s, a_s > a_j$. Specifically, $a_1$ is always a strictly prefix-maximum element of $A$.
2. If $a_s > 1$, insert $(a_s - 1)$ at the end of sequence $A$.
3. Delete the first $s$ elements of sequence $A$.

Consider the following example: for $A = [1, 3, 2, 3, 4]$, Little H can choose $s = 1$, then the modified sequence is $[3, 2, 3, 4]$. Little H can choose $s = 2$, then the modified sequence is $[2, 3, 4, 2]$. * Little H cannot choose $s = 4$, because $a_2 = a_4 = 3$, which means $a_4$ is not a strictly prefix-maximum element.

Little H can perform any number of modification operations, or perform no modifications at all. To break the seal, Little H wants to know: how many different non-empty sequences can he obtain through these modification operations?

Two sequences $A = [a_1, \dots, a_n]$ and $B = [b_1, \dots, b_m]$ are considered different if and only if $n \neq m$ or $\exists 1 \le i \le \min\{n, m\}, a_i \neq b_i$.

Since the answer can be very large, you only need to tell Little H the result modulo $998,244,353$.

Input

The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The following lines contain the test cases.

For each test case, the first line contains two integers $n$ and $m$, representing the length of the sequence and the range of values, respectively. The second line contains $n$ integers $a_1, a_2, \dots, a_n$, describing the sequence $A$.

Output

For each test case, output a single integer on a new line, representing the number of different non-empty sequences that can be obtained, modulo $998,244,353$.

Examples

Input 1

1 4
2 3 2
3 1 2 1
4 3
3 1 2 1
5 4
1 3 2 3 4
7 5
4 4 5 2 3 3 1

Output 1

4
7
20
59

Note 1

The sample contains 4 test cases. For the first test case, the obtainable non-empty sequences are $[1, 2, 1], [2, 1], [1, 1], [1]$. For the second test case, the obtainable non-empty sequences are $[3, 1, 2, 1], [1, 2, 1, 2], [2, 1, 2], [1, 2, 1], [2, 1], [1, 1], [1]$.

Input 2

0 2
11 10
8 8 8 9 9 8 8 9 9 9 8
12 2500
1529 1470 1361 1416 1492 1503 1641 1868 1829 1959 2052 2105

Output 2

694
4961744

Input 3

See seal/seal3.in and seal/seal3.ans in the contestant directory.
This sample satisfies the constraints for test cases 3 ~ 5.

Input 4

See seal/seal4.in and seal/seal4.ans in the contestant directory.
This sample satisfies the constraints for test case 10.

Input 5

See seal/seal5.in and seal/seal5.ans in the contestant directory.
This sample satisfies the constraints for test cases 11 ~ 14.

Input 6

See seal/seal6.in and seal/seal6.ans in the contestant directory.
This sample satisfies the constraints for test case 15.

Input 7

See seal/seal7.in and seal/seal7.ans in the contestant directory.
This sample satisfies the constraints for test cases 17 ~ 19.

Input 8

See seal/seal8.in and seal/seal8.ans in the contestant directory.
This sample satisfies the constraints for test cases 22 ~ 25.

Subtasks

For all test cases: $1 \le T \le 10$ $1 \le n, m \le 2,500$ * $\forall 1 \le i \le n, 1 \le a_i \le m$

Special Property A: $\forall 1 \le i < j \le n, a_i \neq a_j$. Special Property B: $\forall 1 \le i < n, a_i < a_{i+1}$.