In the KMP algorithm, the next array (also known as the LPS array, for Longest Prefix Suffix, or the failure function) is a core concept. Given a string $S = s_1s_2\dots s_n$ of length $n$, its next array $next[1..n]$ is defined such that $next[i]$ represents the length of the longest equal proper prefix and proper suffix of the substring $S[1..i]$, specifically, $next[1] = 0$. Formally, it is defined as:

$$next[i] = \max_{k=0,\dots,i-1} \{k : S[1\dots k] = S[i-k+1\dots i]\}$$

Here, $S[l..r]$ is defined as the substring formed by the $l$-th character to the $r$-th character of the string $S$. It is considered that $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, both of which are empty strings.

Given an array $A[1..n]$ of length $n$. You need to count how many different strings $S$ of length $n$ defined over the character set $\Sigma$ have a next array that is exactly equal to the given array $A$. The size of the character set is $m$. Output the number of such strings modulo $998\,244\,353$.

Input

There are multiple test cases in a single test file. The first line of the input contains a single integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

For each test case:

• The first line contains two integers $n$ ($2 \le n \le 10^5$) and $m$ ($1 \le m \le 10^6$) representing the length of the given array and the size of the character set.
• The second line contains $n$ integers, separated by spaces, representing the given array $A$. It is guaranteed that $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

It is guaranteed that the total sum of $n$ does not exceed $5 \times 10^5$, i.e., $\sum n \le 5 \times 10^5$.

Output

For each test case, output a single line with a single integer, representing the number of strings that satisfy the conditions, with the answer taken modulo $998\,244\,353$.

Example

Input

3
3 3
0 1 2
7 3
0 0 0 1 2 3 0
7 3
0 0 0 1 2 3 1

Output

3
24
0

Note

For the second group of data in the sample, let us assume the character set $\Sigma = \{'a', 'b', 'c'\}$. The $24$ strings that meet the requirements are:

abbabbb abbabbc abcabcb abcabcc acbacbb acbacbc
accaccb accaccc baabaaa baabaac bacbaca bacbacc
bcabcaa bcabcac bccbcca bccbccc caacaaa caacaab
cabcaba cabcabb cbacbaa cbacbab cbbcbba cbbcbbb