题目描述

在《我的世界》这个充满无限可能的沙盒世界中，我们的主人公Steve，一位勇敢的探险家和建造大师，决定接受一项全新的挑战——成为一名汽车经销商的销售员。在这个平行世界中，汽车经销商拥有 $n$ 种不同型号的汽车，每种型号的汽车数量各不相同。第 $i$ 种型号的汽车有 $a_i$ 辆。Steve作为一名出色的销售员，他拥有一项特殊能力：可以说服顾客一次性购买最多 $x$ 辆汽车（Steve可以自由选择车型），但要求这些汽车必须来自不同的车型。 在这个充满挑战的新角色中，Steve需要你的帮助来计算，他至少需要带来多少位顾客，才能将所有汽车全部售出。这是一个考验策略和计算能力的问题，你需要帮助Steve制定出最有效的销售计划。

输入格式

每个测试用例包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。

每组测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 5 \cdot 10^5$，$1 \le x \le 10$），分别表示不同车型的数量和Steve能说服一位顾客购买的最多汽车数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每种车型的汽车数量。

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

输出格式

对于每组测试用例，输出一个整数，表示售出所有汽车所需的最少顾客数。

输入输出样例 #1

输入 #1

4
3 2
3 1 2
3 3
2 1 3
5 3
2 2 1 9 2
7 4
2 5 3 3 5 2 5

输出 #1

3
3
9
7

说明/提示

对于第一个样例，Steve只需要带来 $3$ 位顾客。他可以让顾客购买如下车型的汽车：

• 顾客 $1$ 购买 $2$ 辆汽车，分别来自车型 $1$ 和 $3$。
• 顾客 $2$ 购买 $2$ 辆汽车，分别来自车型 $1$ 和 $2$。
• 顾客 $3$ 购买 $2$ 辆汽车，分别来自车型 $1$ 和 $3$。

对于第二个样例，Steve只需要带来 $3$ 位顾客。他可以让顾客购买如下车型的汽车：

• 顾客 $1$ 购买 $2$ 辆汽车，分别来自车型 $1$ 和 $3$。
• 顾客 $2$ 购买 $3$ 辆汽车，分别来自车型 $1$、$2$ 和 $3$。
• 顾客 $3$ 购买 $1$ 辆汽车，来自车型 $3$。