题目描述
给定含 n 个元素的可重集 S={s1,…,sn} 和整数 k。
一次操作可以从 S 中选择一个子可重集 S′,将所选元素从 S 中移除,然后向 S 中加入一个数 mex(S′)。允许选择空集。
这里 mex 是集合中没有出现过的最小非负整数。例如 mex{0,1,2}=3,mex{1,0,3,1}=2,mex∅=0。重复元素可以分别选取或保留。
求把 S 变成只含一个元素 k 的可重集 {k} 所需的最少操作次数,对 998244353 取模。可以证明总存在可行方案。应先最小化实际次数,再对答案取模。
输入格式
第一行一个整数 t。每组第一行两个整数 n,k,第二行 n 个整数 s1,…,sn。
1≤t≤105,1≤n≤5⋅105,0≤k,si≤109;所有组的 n 之和不超过 5⋅105。
输出格式
每组输出一行,表示最少操作次数对 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