CF1704C.Virus

There are $n$ houses numbered from $1$ to $n$ on a circle. For each $1 \leq i \leq n - 1$, house $i$ and house $i + 1$ are neighbours; additionally, house $n$ and house $1$ are also neighbours.

Initially, $m$ of these $n$ houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently.

Every day, the following things happen in order:

• Cirno chooses an uninfected house, and protect it permanently.
• All uninfected, unprotected houses which have at least one infected neighbor become infected.

Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect.

Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever.

有 $n$ 座房屋按顺时针编号为 $1$ 到 $n$，围成一个圆圈。对于每个 $1 \leq i \leq n - 1$，房屋 $i$ 与房屋 $i + 1$ 相邻；此外，房屋 $n$ 与房屋 $1$ 也相邻。

初始时，这 $n$ 座房屋中有 $m$ 座已被一种致命病毒所感染。

每天清晨，Cirno 可以选择一座未被感染的房屋，并永久性地保护该房屋，使其永远不被感染。

每一天内，以下事件按顺序发生：

• Cirno 选择一座未被感染的房屋，并永久性地保护它；
• 所有未被感染且未受保护的房屋中，只要存在至少一个已被感染的邻居，就会在当天被感染。

Cirno 希望阻止病毒进一步传播。若她以最优策略选择需保护的房屋，请问最终被感染的房屋数量的最小值是多少？

注意：Cirno 每天总是在病毒传播之前选择一座房屋进行保护；且一旦某座房屋被保护，它将永远不会被感染。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of test cases follows.

The first line of each test case consists of two positive integers $n, m$ ($5 \leq n \leq 10^9$, $1 \leq m \leq \min(n, 10^5)$) — the number of houses on the circle, and the number of houses that are initially infected.

The second line of each test case consists of $m$ distinct positive integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$) — the indices of the houses infected initially.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end.

对于每个测试用例，在单独一行输出一个整数，表示最终被感染房屋的最小数量。

In the first test case:

At the start of the first day, house $3$, $6$, $8$ are infected. Choose house $2$ to protect.

At the start of the second day, house $3$, $4$, $5$, $6$, $7$, $8$, $9$ are infected. Choose house $10$ to protect.

At the start of the third day, no more houses are infected.

In the second test case:

At the start of the first day, house $2$, $5$ are infected. Choose house $1$ to protect.

At the start of the second day, house $2$, $3$, $4$, $5$, $6$ are infected. No more available houses can be protected.

在第一个测试用例中：

第一天开始时，房屋 $3$、$6$、$8$ 已被感染。选择保护房屋 $2$。

第二天开始时，房屋 $3$、$4$、$5$、$6$、$7$、$8$、$9$ 已被感染。选择保护房屋 $10$。

第三天开始时，不再有新的房屋被感染。

在第二个测试用例中：

第一天开始时，房屋 $2$、$5$ 已被感染。选择保护房屋 $1$。

第二天开始时，房屋 $2$、$3$、$4$、$5$、$6$ 已被感染。已无更多可保护的房屋。