一个圆圈上有 $$$n$$$ 栋房屋,编号从 $$$1$$$ 到 $$$n$$$。对于每个 $$$1 \leq i \leq n - 1$$$,房子 $$$i$$$ 和房子 $$$i + 1$$$ 是邻居;此外,房子$$$n$$$ 和房子$$$1$$$ 也是邻居。
最初,这些 $$$n$$$ 房屋中的 $$$m$$$ 被致命病毒感染。每天早上,琪露诺都可以选择一所没有被感染的房屋,并永久保护该房屋不被感染。
每天,以下事情按顺序发生:
- 琪露诺选择一所未受感染的房屋,并永久保护它。
- 所有至少有一名受感染邻居的未受感染、不受保护的房屋都会受到感染。
琪露诺想要阻止病毒传播。如果她最优地选择要保护的房屋,求最终会被感染的最少房屋数量。
请注意,琪露诺每天都会在病毒传播之前选择要保护的房子。此外,受保护的房屋不会永远受到感染。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,单独一行输出一个整数,即最终受感染房屋的最小数量。
示例
输入 #1
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
输出 #1
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$$$ 被感染。没有更多的可用房屋可以得到保护。