A. LuoTianyi и шоу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В шоу о VOCALOID принимают участие $$$n$$$ человек. Они будут сидеть в ряду с сиденьями, пронумерованными от $$$1$$$ до $$$m$$$ слева направо.

Все $$$n$$$ людей приходят и садятся по порядку. Каждый человек занимает место одним из трёх способов:

  1. Сесть на соседнее слева место от самого левого человека, который уже сидит, или, если место $$$1$$$ занятно, то покинуть шоу. Если сейчас никто не сидит, то занять место с номером $$$m$$$.
  2. Сесть на соседнее справа место от самого правого человека, который уже сидит, или, если место $$$m$$$ занятно, то покинуть шоу. Если сейчас никто не сидит, то занять место с номером $$$1$$$.
  3. Сесть на место с номером $$$x_i$$$. Если это место занято, то покинуть шоу.

Теперь вы хотите узнать, каково максимальное количество тех, кто может занять место, если вы можете впустить людей на шоу в любом порядке?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — количество людей и количество мест.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$-2 \le x_i \le m$$$, $$$x_i \ne 0$$$), $$$i$$$-е из которых описывает способ, как $$$i$$$-й человек занимает место:

  1. Если $$$x_i=-1$$$, то $$$i$$$-й человек занимает место первым способом.
  2. Если $$$x_i=-2$$$, то $$$i$$$-й человек занимает место вторым способом.
  3. Если $$$x_i > 0$$$, то $$$i$$$-й человек занимает место третьим способом, т.е. хочет сесть на место с номером $$$x_i$$$ или покинуть шоу, если оно занято.

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

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

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

Пример
Входные данные
10
3 10
5 5 5
4 6
1 -2 -2 1
5 7
-1 -1 4 -2 -2
6 7
5 -2 -2 -2 -2 -2
6 6
-1 1 4 5 -1 4
6 8
-1 -1 -1 3 -1 -2
6 7
5 -1 -2 -2 -2 -2
3 1
-2 -2 1
2 5
5 -2
1 2
-1
Выходные данные
1
3
5
6
5
5
5
1
2
1
Примечание

В первом наборе входных данных все люди хотят занять место $$$5$$$, поэтому только $$$1$$$ человек сможет занять место.

Во втором наборе входных данных людей можно впустить в порядке $$$1, 2, 3, 4$$$, тогда все люди, кроме последнего, смогут занять место.

В третьем наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим третьего человека:

–––3–––

Впустим четвёртого человека:

–––34––

Впустим пятого человека:

–––345–

Впустим первого человека:

––1345–

Впустим второго человека:

–21345–

Таким образом, все $$$5$$$ человек заняли места.

В пятом наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим четвёртого человека:

––––4–

Впустим третьего человека:

–––34–

Впустим шестого человека, он покинет шоу, потому что занимает место третьим способом и должен сесть на место $$$4$$$, но оно уже занято:

–––34–

Впустим пятого человека:

––534–

Впустим первого человека:

–1534–

Впустим второго человека:

21534–

Таким образом, $$$5$$$ человек заняли места.

В седьмом наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим третьего человека:

3––––––

Впустим четвёртого человека:

34–––––

Впустим пятого человека:

345––––

Впустим шестого человека:

3456–––

Впустим первого человека:

34561––

Впустим второго человека, он покинет шоу, потому что занимает место первым способом, но место $$$1$$$ занято:

34561––

Таким образом, $$$5$$$ человек заняли места.