CF1496B.Max and Mex

You are given a multiset $S$ initially consisting of $n$ distinct non-negative integers. A multiset is a set, that can contain some elements multiple times.

You will perform the following operation $k$ times:

• Add the element $\lceil\frac{a+b}{2}\rceil$ (rounded up) into $S$, where $a = \operatorname{mex}(S)$ and $b = \max(S)$. If this number is already in the set, it is added again.

Here $\operatorname{max}$ of a multiset denotes the maximum integer in the multiset, and $\operatorname{mex}$ of a multiset denotes the smallest non-negative integer that is not present in the multiset. For example:

• $\operatorname{mex}({1,4,0,2})=3$;
• $\operatorname{mex}({2,5,1})=0$.

Your task is to calculate the number of distinct elements in $S$ after $k$ operations will be done.

给你一个多重集 $S$，初始时包含 $n$ 个互不相同的非负整数。多重集是一种允许元素重复出现的集合。

你将执行以下操作 $k$ 次：

• 向 $S$ 中添加元素 $\lceil\frac{a+b}{2}\rceil$（向上取整），其中 $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$ 中不同元素的个数。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1\le n\le 10^5$, $0\le k\le 10^9$) — the initial size of the multiset $S$ and how many operations you need to perform.

The second line of each test case contains $n$ distinct integers $a_1,a_2,\dots,a_n$ ($0\le a_i\le 10^9$) — the numbers in the initial multiset.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print the number of distinct elements in $S$ after $k$ operations will be done.

对于每个测试用例，输出执行 $k$ 次操作后集合 $S$ 中不同元素的个数。

In the first test case, $S={0,1,3,4}$, $a=\operatorname{mex}(S)=2$, $b=\max(S)=4$, $\lceil\frac{a+b}{2}\rceil=3$. So $3$ is added into $S$, and $S$ becomes ${0,1,3,3,4}$. The answer is $4$.

In the second test case, $S={0,1,4}$, $a=\operatorname{mex}(S)=2$, $b=\max(S)=4$, $\lceil\frac{a+b}{2}\rceil=3$. So $3$ is added into $S$, and $S$ becomes ${0,1,3,4}$. The answer is $4$.

在第一个测试用例中，$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$。