题目描述

Yuki has a multiset $S = \{s_1, \dots, 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}^\ast$ 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\}$.

$^\ast$: The $\operatorname{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$.

输入格式

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\cdot10^5,\ 0 \le k \le 10^9)$.
• The second line contains $n$ integers $s_1, \dots, 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$.

输出格式

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

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

2
0
3
2
1
262875292

提示

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