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

На круге находятся $$$n$$$ домов с номерами от $$$1$$$ до $$$n$$$. Для каждого $$$1 \leq i \leq n - 1$$$ дом $$$i$$$ и дом $$$i + 1$$$ являются соседями; кроме того, дом $$$n$$$ и дом $$$1$$$ также являются соседями.

Изначально $$$m$$$ из этих $$$n$$$ домов заражены смертельным вирусом. Каждое утро Cirno может выбрать незараженный дом и навсегда защитить его от заражения.

Каждый день по порядку происходят следующие вещи:

  • Cirno выбирает незараженный дом и защищает его навсегда.
  • Заражаются все незараженные и незащищенные дома, у которых есть хотя бы один зараженный сосед.

Cirno хочет остановить распространение вируса. Найдите минимальное количество домов, которые в итоге будут заражены, если вы оптимально выберете дома для защиты.

Обратите внимание, что каждый день Cirno всегда выбирает дом для защиты до распространения вируса. Также защищенный дом не будет никогда заражен.

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

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

Первая строка каждого набора входных данных состоит из двух целых положительных чисел $$$n, m$$$ ($$$5 \leq n \leq 10^9$$$, $$$1 \leq m \leq \min(n, 10^5)$$$) — количество домов в круге и количество домов, которые изначально заражены.

Вторая строка каждого набора входных данных состоит из $$$m$$$ различных положительных целых чисел $$$a_1, a_2, \cdots , a_m$$$ ($$$1 \leq a_i \leq n$$$) — индексы первоначально зараженных домов.

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

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

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

Пример
Входные данные
8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16
Выходные данные
7
5
11
28
9
5
2
15
Примечание

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

В начале первого дня заражены дома $$$3$$$, $$$6$$$, $$$8$$$. Выберите дом $$$2$$$ для защиты.

В начале второго дня заражены дома $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$. Выберите дом $$$10$$$ для защиты.

В начале третьего дня зараженных домов больше нет.

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

В начале первого дня заражены дома $$$2$$$, $$$5$$$. Выберите дом $$$1$$$ для защиты.

В начале второго дня заражены дома $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$. Не осталось незащищенных и незараженных домов.