B. Max и Mex
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано мультимножество $$$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$$$.

Ваша задача — вычислить количество различных элементов в $$$S$$$ после выполнения $$$k$$$ операций.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите количество различных элементов в $$$S$$$ после выполнения $$$k$$$ операций.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$S=\{0,1,3,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. Поэтому в $$$S$$$ добавляется число $$$3$$$, а $$$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$$$. Поэтому в $$$S$$$ добавляется число $$$3$$$, а $$$S$$$ становится равным $$$\{0,1,3,4\}$$$. Таким образом, ответ равен $$$4$$$.