题目描述

为了庆祝康复，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$ 的砂锅分成长度为 $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 切出的每块砂锅的长度。

保证所有测试用例中 $k$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，输出 k1o0n 恢复砂锅所需的最少操作次数。

说明/提示

由 ChatGPT 4.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

2
3
9
15