为了庆祝他的康复,k1o0n 烘烤了一个巨大的 $$$n$$$ 米长的土豆砂锅。
事实证明,Noobish_Monk 就是无法忍受土豆,所以他决定毁了 k1o0n 的饭菜。他将其切成 $$$k$$$ 块,长度为 $$$a_1, a_2, \dots, a_k$$$ 米。
k1o0n 对此并不热衷。幸运的是,一切都可以解决。为此,k1o0n 可以执行以下操作之一:
- 选择长度为 $$$a_i \ge 2$$$ 的一块,并将其分成长度为 $$$1$$$ 和 $$$a_i - 1$$$ 的两块。这样一来,件数就会增加$$$1$$$;
- 选择一个切片 $$$a_i$$$ 和另一个长度为 $$$a_j=1$$$ ($$$i \ne j$$$) 的切片,并将它们合并为一个长度为 $$$a_i+1$$$ 的切片。结果,件数将减少$$$1$$$。
帮助 k1o0n 找到他需要执行的最少操作次数,才能将砂锅合并成长度为 $$$n$$$ 的一块。
例如,如果 $$$n=5$$$、$$$k=2$$$ 且 $$$a = [3, 2]$$$,则最好执行以下操作:
1. 将长度为 $$$2$$$ 的片段分成长度为 $$$2-1=1$$$ 和 $$$1$$$ 的两片段,结果 $$$a = [3, 1, 1]$$$。
2. 将长度为$$$3$$$的片段与长度为$$$1$$$的片段合并,得到$$$a = [4, 1]$$$。
3. 将长度为$$$4$$$的片段与长度为$$$1$$$的片段合并,结果$$$a = [5]$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。
每个测试用例的描述由两行组成。第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$2 \le k \le 10^5$$$) — 砂锅的长度和件数。
第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n - 1$$$, $$$\sum a_i = n$$$) — Noobish_Monk 切割的砂锅菜块的长度。
保证所有 $$$t$$$ 测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 K1o0n 在 Noobish_Monk 的恐怖之后恢复其馅饼所需的最小操作数。
示例
输入 #1
4 5 3 3 1 1 5 2 3 2 11 4 2 3 1 5 16 6 1 6 1 1 1 6
输出 #1
2 3 9 15