题目描述

Yuki 有一个大小为 $n$ 的可重集合 $S = \{s_1, \dots, s_n\}$ 和一个整数 $k$。

Yuki 定义一次变换为：

• 选择 $S$ 的一个子集 $S'$（$S'$ 可以为空集），将 $S'$ 从 $S$ 中删除，并将 $S'$ 的 $\operatorname{mex}^\ast$ 添加到 $S$ 中。

现在，Yuki 想进行若干次变换，使得 $S$ 变为 $\{k\}$。你需要帮助 Yuki 求出，使 $S$ 变为 $\{k\}$ 所需的最小变换次数。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果即可。

可以证明，一定存在至少一种操作方案能够使 $S$ 变为 $\{k\}$。

$^\ast$：一个可重集的 $\operatorname{mex}$ 为该可重集中未出现过的最小非负整数，例如 $\operatorname{mex}\{0,1,2\} = 3$，$\operatorname{mex}\{1,0,3,1\} = 2$，$\operatorname{mex} \varnothing = 0$。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n, k$ $(1 \le n \le 5\cdot10^5,\ 0 \le k \le 10^9)$。
• 第二行包含 $n$ 个整数 $s_1, \dots, s_n$ $(0 \le s_i \le 10^9)$。

保证所有测试数据中 $n$ 的总和不超过 $5\cdot 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示使 $S$ 变为 $\{k\}$ 所需的最小变换次数对 $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

提示

对于第 $1$ 组测试数据：

• Yuki 可以在第 $1$ 次变换中选择 $S' = \varnothing$，使 $S$ 变为 $\{0,1\}$，再在第 $2$ 次变换中选择 $S' = \{0,1\}$，使 $S$ 变为 $\{2\}$。
• 可以证明，不存在变换次数更少的操作方案，因此答案为 $2$。

对于第 $2$ 组测试数据：

• Yuki 不需要进行变换即可使 $S = \{4\}$，因此答案为 $0$。

对于第 $3$ 组测试数据：

• Yuki 可以在第 $1$ 次变换中选择 $S' = \varnothing$，使 $S$ 变为 $\{0,0,2,2\}$，在第 $2$ 次变换中选择 $S' = \{0,2\}$，使 $S$ 变为 $\{0,1,2\}$，再在第 $3$ 次变换中选择 $S' = \{0,1,2\}$，使 $S$ 变为 $\{3\}$。
• 可以证明，不存在变换次数更少的操作方案，因此答案为 $3$。

对于第 $4$ 组测试数据：

• Yuki 可以在第 $1$ 次变换中选择 $S' = \{2,3\}$，使 $S$ 变为 $\{0,0,1\}$，再在第 $2$ 次变换中选择 $S' = \{0,0,1\}$，使 $S$ 变为 $\{2\}$。
• 可以证明，不存在变换次数更少的操作方案，因此答案为 $2$。

对于第 $5$ 组测试数据：

• Yuki 可以直接在第 $1$ 次变换中选择 $S' = \{0,1,2,2\}$，使 $S$ 变为 $\{3\}$。
• 可以证明，不存在变换次数更少的操作方案，因此答案为 $1$。