题目描述

题目链接

给出一个长度大小为 $n$ 的可重集合 $S$（集合内允许有），保证这 $n$ 个数互不相同且非负。

接下来，你需要将下面操作进行 $k$ 次：
将 $\lceil \frac{a+b}{2}\rceil$ 加入集合（注意这里是可重集），其中 $a=\operatorname{mex}(S)$， $b=\max(S)$。

这里 $\operatorname{mex}(S)$ 表示集合 $S$ 中没有出现过的最小的非负整数，$\max(S)$ 表示 $S$ 中的最大整数。

求 $k$ 次操作后，集合 $S$ 中有多少个不同的数。

输入格式

本题有多组数据
第一行一个整数 $T$，表示数据的组数。
对于每组数据：
第一行两个整数 $n,k$，表示集合初始长度和操作次数。
第二行 $n$ 个整数，表示 $a_{1 \dots n}$。

输出格式

对于每组数据，输出一行一个整数表示答案。

说明/提示

$1\le T \le 100$
$1\le n \le 10^5$
$0 \le a_i,k \le 10^9$
$\sum n\le 10^5$

样例

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

4
4
3
5
3