P17300 [ICPC 2026 Xi'an I] Transform

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

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