您正在玩一款游戏,您的角色应该克服不同的障碍。当前的问题是如何从悬崖上下来。悬崖的高度为$$$h$$$,从$$$1$$$到$$$h$$$的每个高度$$$x$$$上都有一个移动平台。
每个平台要么隐藏在悬崖内,要么移出。首先,有 $$$n$$$ 移出高度为 $$$p_1、p_2、\dots、p_n$$$ 的平台。高度 $$$h$$$ 的平台被移出(角色最初站在那里)。
如果你的角色站在高度 $$$x$$$ 的某个移出的平台上,那么他可以拉动一个特殊的杠杆,这会切换两个平台的状态:高度 $$$x$$$ 和 $$$x - 1$$$。换句话说,你当前所站的平台会隐藏在悬崖中,而下方一个单位的平台会改变其状态:移出则隐藏,隐藏则移出。在第二种情况下,您将安全着陆。请注意,这是从一个平台转移到另一个平台的唯一方法。
你的角色非常脆弱,所以它可以安全地从不超过$$$2$$$的高度坠落。换句话说,从 $$$x$$$ 平台跌落到 $$$x - 2$$$ 平台是可以的,但从 $$$x$$$ 跌落到 $$$x - 3$$$ (或更低)则必死无疑。
有时不可能从悬崖上下来,但你总是可以购买(捐赠货币)一些魔法水晶。每个魔法水晶都可以用来改变任何单个平台的状态(高度 $$$h$$$ 的平台除外,它不受水晶的影响)。使用后,水晶就会消失。
安全降落在$$$0$$$地面上至少需要购买多少魔水晶?
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。每个查询包含两行并且独立于所有其他查询。
每个查询的第一行包含两个整数 $$$h$$$ 和 $$$n$$$ ($$$1 \le h \le 10^9$$$, $$$1 \le n \le \min(h, 2 \cdot 10^5)$$$) — 悬崖的高度和移出平台的数量。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$h = p_1 > p_2 > \dots > p_n \ge 1$$$) — 相应的移出平台按高度降序排列。
所有查询的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,打印一个整数——安全降落到地面(高度 $$$0$$$)所需的最少魔法水晶数量。
示例
输入 #1
4 3 2 3 1 8 6 8 7 6 5 3 2 9 6 9 8 5 4 3 1 1 1 1
输出 #1
0 1 2 0