给定一个多重集 $$$S$$$,最初由 $$$n$$$ 不同的非负整数组成。多重集是一个可以多次包含某些元素的集合。
您将执行以下操作 $$$k$$$ 次:
- 将元素 $$$\lceil\frac{a+b}{2}\rceil$$$ (向上舍入)添加到 $$$S$$$ 中,其中 $$$a = \operatorname{mex}(S)$$$ 和 $$$b = \max(S)$$$。如果该数字已在集合中,则会再次添加。
这里多重集的 $$$\operatorname{max}$$$ 表示多重集中的最大整数,多重集的 $$$\operatorname{mex}$$$ 表示多重集中不存在的最小非负整数。例如:
- $$$\operatorname{mex}(\{1,4,0,2\})=3$$$;
- $$$\operatorname{mex}(\{2,5,1\})=0$$$。
您的任务是在完成 $$$k$$$ 操作后计算 $$$S$$$ 中不同元素的数量。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1\le n\le 10^5$$$, $$$0\le k\le 10^9$$$) - 多重集 $$$S$$$ 的初始大小以及需要执行的操作数量。
每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 10^9$$$) - 初始多重集中的数字。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,在完成 $$$k$$$ 操作后打印 $$$S$$$ 中不同元素的数量。
示例
输入 #1
5 4 1 0 1 3 4 3 1 0 1 4 3 0 0 1 4 3 2 0 1 2 3 2 1 2 3
输出 #1
4 4 3 5 3
注意
在第一个测试用例中,$$$S=\{0,1,3,4\}$$$、$$$a=\operatorname{mex}(S)=2$$$、$$$b=\max(S)=4$$$、$$$\lceil\frac{a+b}{2}\rceil=3$$$。所以$$$3$$$被添加到$$$S$$$中,$$$S$$$变成$$$\{0,1,3,3,4\}$$$。答案是$$$4$$$。
在第二个测试用例中,$$$S=\{0,1,4\}$$$、$$$a=\operatorname{mex}(S)=2$$$、$$$b=\max(S)=4$$$、$$$\lceil\frac{a+b}{2}\rceil=3$$$。所以$$$3$$$被添加到$$$S$$$中,$$$S$$$变成$$$\{0,1,3,4\}$$$。答案是$$$4$$$。