Yuki has a multiset $S=\{s_1,\ldots,s_n\}$ of size $n$ and an integer $k$.

Yuki defines a transformation as follows:

• Choose a subset $S'$ of $S$ (where $S'$ can be an empty set), remove $S'$ from $S$, and add the $\operatorname{mex}^{*}$ of $S'$ to $S$.

Now, Yuki wants to perform several transformations such that $S$ becomes $\{k\}$. You need to help Yuki find the minimum number of transformations required to make $S$ equal to $\{k\}$. Since the answer can be very large, you only need to output the answer modulo $998244353$.

It can be proven that there always exists at least one sequence of operations that can transform $S$ into $\{k\}$.

$*$: The mex of a multiset is the smallest non-negative integer that does not appear in the multiset. For example, $\operatorname{mex}\{0,1,2\}=3$, $\operatorname{mex}\{1,0,3,1\}=2$, and $\operatorname{mex}\varnothing=0$.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t$ ($1 \le t \le 10^5$), representing the number of test cases.

For each test case:

• The first line contains two integers $n,k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le 10^9$).
• The second line contains $n$ integers $s_1,\ldots,s_n$ ($0 \le s_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a single line containing an integer representing the minimum number of transformations required to make $S$ equal to $\{k\}$, modulo $998244353$.

Examples

Input 1

6
1 2
1
1 4
4
3 3
0 2 2
4 2
1 0 3 2
4 3
2 1 0 2
3 52
20 2 6

Output 1

2
0
3
2
1
262875292

Note

For the 1st test case:

• Yuki can choose $S'=\varnothing$ in the 1st transformation, making $S=\{0,1\}$, and then choose $S'=\{0,1\}$ in the 2nd transformation, making $S=\{2\}$.
• It can be proven that no sequence of operations with fewer transformations exists, so the answer is $2$.

For the 2nd test case:

• Yuki does not need to perform any transformations to make $S=\{4\}$, so the answer is $0$.

For the 3rd test case:

• Yuki can choose $S'=\varnothing$ in the 1st transformation, making $S=\{0,0,2,2\}$, choose $S'=\{0,2\}$ in the 2nd transformation, making $S=\{0,1,2\}$, and then choose $S'=\{0,1,2\}$ in the 3rd transformation, making $S=\{3\}$.
• It can be proven that no sequence of operations with fewer transformations exists, so the answer is $3$.

For the 4th test case:

• Yuki can choose $S'=\{2,3\}$ in the 1st transformation, making $S=\{0,0,1\}$, and then choose $S'=\{0,0,1\}$ in the 2nd transformation, making $S=\{2\}$.
• It can be proven that no sequence of operations with fewer transformations exists, so the answer is $2$.

For the 5th test case:

• Yuki can directly choose $S'=\{0,1,2,2\}$ in the 1st transformation, making $S=\{3\}$.
• It can be proven that no sequence of operations with fewer transformations exists, so the answer is $1$.