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

Алиса и Боб играют в игру. На доске написано $$$n$$$ ($$$n$$$ четное) целых чисел $$$x_1, x_2, \ldots, x_n$$$. Также дано целое число $$$k$$$ и целое число score, которое изначально равно $$$0$$$. Игра длится $$$\frac{n}{2}$$$ ходов, в которых последовательно происходят следующие события:

  • Алиса выбирает целое число с доски и стирает его. Назовем выбранное Алисой число $$$a$$$.
  • Боб выбирает целое число с доски и стирает его. Назовем выбранное Бобом число $$$b$$$.
  • Если $$$a+b=k$$$, добавляем $$$1$$$ к score.

Алиса играет, чтобы минимизировать score, в то время как Боб играет, чтобы максимизировать score. Предполагая, что оба игрока используют оптимальные стратегии, каков будет score после окончания игры?

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq n$$$) — числа на доске.

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

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

Для каждого набора входных данных выведите score, если оба игрока играют оптимально.

Пример
Входные данные
4
4 4
1 2 3 2
8 15
1 2 3 4 5 6 7 8
6 1
1 1 1 1 1 1
16 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
Выходные данные
2
1
0
4
Примечание

В первом наборе входных данных один из возможных сценариев игры выглядит следующим образом:

  • Алиса выбирает $$$1$$$, а Боб выбирает $$$3$$$. Счет увеличивается, так как $$$1+3=4$$$. Теперь на доске остаются два целых числа $$$2$$$ и $$$2$$$.
  • Алиса и Боб оба выбирают $$$2$$$. Счет увеличивается, так как $$$2+2=4$$$.
  • Игра заканчивается, так как на доске больше нет целых чисел.

В третьем наборе входных данных невозможно, чтобы сумма выбранных Алиской и Бобом целых чисел была равна $$$1$$$, поэтому мы отвечаем $$$0$$$.

Обратите внимание, что это всего лишь пример того, как может проходить игра для демонстрационных целей. Это может не быть самыми оптимальными стратегиями Алисы или Боба.