Background

农夫的好帮手——乔治，他喜欢在游戏里造桥和砍树。

乔治在玩一款休闲模拟类游戏。他在游戏中出生的地区是一片群岛，具体的来说，一共有 $n$ 座岛屿，而乔治一开始生活在 $1$ 号岛屿。岛屿和岛屿之间互不连通。

游戏中，第 $i$ 座岛屿有 $t_i$ 根树，乔治伐一根树就可以获得一根圆木。由于游戏的刷新机制，所有的岛屿每天早上都会恢复原状。也就是说，第 $i$ 座岛屿的树数量都会被设置为 $t_i$ 根。

乔治每天可以修建一座桥，以将任意两个岛屿连接起来。岛屿之间修桥必须至少有一个是他当前可以到达的。他希望能尽快将所有岛屿连通。显然，这需要 $n - 1$ 天。造桥本身不需要消耗圆木，乔治有其他材料可用，可是他有一个爱好，是砍树。当地连接岛屿 $u$ 和 $v$ 的桥时，他一定会在造桥的当天把岛 $u$ 和 $v$ 上的树全都砍掉，共获得 $t_u + t_v$ 根圆木。（当然，这天过后岛上的树又会恢复）

游戏里有一个合成公式，每使用 $k$ 根圆木，就可以合成一根硬木，这个合成操作每天可以做任意多次。合成的硬木可以在每天晚上卖给市场获得收益，但是剩余的圆木每天都会被系统清空。乔治不在乎自己能获得多少钱，但是患有强迫症的他很讨厌自己辛苦获得的圆木被浪费掉。

所以，现在你需要帮助他解决这个问题：请你安排好每天的造桥计划，使得第 $n-1$ 天后所有岛屿可以相互到达，并且最小化这 $n-1$ 天里被系统清空的圆木总数，你只需要输出这个最小总数即可。

Format

Input

本题有多组输入，第一行输入一个正整数 $T$ 表示输入组数。
接下来，对于每组输入：

• 第一行，输入 $2$ 个正整数，$n(1 \leq n \leq 10^5)$，$k(1 \leq k \leq 10^9)$，分别表示岛屿数量和合成一根硬木所需的圆木数量。
• 第二行，输入 $n$ 个正整数，第 $i$ 个数为 $t_i(0 \leq t_i \leq 10^9)$，表示每天第 $i$ 座岛上的树的棵数。

数据保证，输入的 $n$ 的总和不超过 $2 \times 10^5$，即 $\sum n \leq 2 \times 10^5$。

Output

输出 $T$ 行，每行一个整数，表示对应的答案。

Samples

2
5 3
1 2 3 4 5
8 7
3 1 4 1 5 9 2 6

1
2

Note

对于样例中的第二组数据，建桥的示意图如下图所示。
具体来说，一种可行的建桥方案为：

• 第 1 天，连接 1 号岛屿和 5 号岛屿，获得 $3+5$ 根圆木，合成 1 根硬木，剩余 1 根圆木；
• 第 2 天，连接 1 号岛屿和 3 号岛屿，获得 $3+4$ 根圆木，合成 1 根硬木，剩余 0 根圆木；
• 第 3 天，连接 5 号岛屿和 7 号岛屿，获得 $5+2$ 根圆木，合成 1 根硬木，剩余 0 根圆木；
• 第 4 天，连接 5 号岛屿和 6 号岛屿，获得 $5+9$ 根圆木，合成 2 根硬木，剩余 0 根圆木；
• 第 5 天，连接 6 号岛屿和 8 号岛屿，获得 $9+6$ 根圆木，合成 2 根硬木，剩余 1 根圆木；
• 第 6 天，连接 8 号岛屿和 4 号岛屿，获得 $6+1$ 根圆木，合成 1 根硬木，剩余 0 根圆木；
• 第 7 天，连接 8 号岛屿和 2 号岛屿，获得 $6+1$ 根圆木，合成 1 根硬木，剩余 0 根圆木。

因此一共浪费 2 根圆木，可以证明没有比这更优的方案。

数据保证，输入的 $n$ 的总和不超过 $2 \times 10^5$，即 $\sum n \leq 2 \times 10^5$。