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

Вам дан массив $$$a$$$ длины $$$n$$$ и чётное число $$$k$$$ ($$$2 \le k \le n$$$). Вам требуется разбить массив $$$a$$$ на ровно $$$k$$$ непустых подмассивов$$$^{\dagger}$$$ так, чтобы каждый элемент массива $$$a$$$ принадлежал ровно одному подмассиву.

Далее все подмассивы с чётными номерами (второй, четвёртый, $$$\ldots$$$, $$$k$$$-й) склеивают в один массив $$$b$$$. После этого в конец массива $$$b$$$ добавляют $$$0$$$.

Стоимостью массива $$$b$$$ называется минимальный индекс $$$i$$$, такой что $$$b_i \neq i$$$. Например, стоимость массива $$$b = [1, 2, 4, 5, 0]$$$ равна $$$3$$$, т.к. $$$b_1 = 1$$$, $$$b_2 = 2$$$, $$$b_3 \neq 3$$$. Определите минимальную стоимость массива $$$b$$$, которую можно получить при оптимальном разбиении массива $$$a$$$ на подмассивы.

$$$^{\dagger}$$$Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ — чётное) — длина массива $$$a$$$ и количество подмассивов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — минимальную стоимость массива $$$b$$$, которую можно получить при оптимальном разбиении.

Пример
Входные данные
4
3 2
1 1 1
8 8
1 1 2 2 3 3 4 4
5 4
1 1 1 2 2
5 4
1 1 1000000000 2 2
Выходные данные
2
5
2
1
Примечание

В первом наборе входных данных существует всего два возможных разбиения: $$$[[1], [1, 1]]$$$ и $$$[[1, 1], [1]]$$$. В любом случае $$$b_1 = 1$$$, а $$$b_2 \ne 2$$$, поэтому стоимость равна $$$2$$$.

Во втором наборе входных данных существует единственное возможное разбиение, при котором $$$b = [1, 2, 3, 4, 0]$$$, поэтому стоимость равна $$$5$$$ ($$$b_5 = 0 \ne 5$$$).

В третьем наборе входных данных подходит следующее разбиение: $$$[[1], [1, 1], [2], [2]]$$$. Тогда $$$b = [1, 1, 2, 0]$$$, и стоимость равна $$$2$$$.