Qiao is a farmer who loves building bridges and chopping trees in games.

Qiao is playing a casual simulation game. In the game, the area where he lives is an archipelago, specifically consisting of $n$ islands, and Qiao starts living on island 1. Initially, there are no bridges between the islands.

In the game, the $i$-th island has $t_i$ trees, and chopping down one tree yields one log. Due to the game's respawn mechanism, all islands refresh their trees every morning, meaning that every morning the number of trees on the $i$-th island is set to $t_i$.

Qiao can build one bridge every day, connecting any two islands (of course, these two islands must be such that at least one of them is currently reachable from his starting point). He hopes to connect all islands as soon as possible; obviously, this takes $n-1$ days. Building a bridge itself does not consume logs, and Qiao has no other materials to use, but he has a hobby: chopping trees. When he builds a bridge connecting islands $u$ and $v$, he will chop down all the trees on islands $u$ and $v$ on that day, obtaining a total of $t_u + t_v$ logs. (Of course, after that day, the trees on the islands will be restored.)

The game has a synthesis formula: using $k$ logs, one can synthesize one piece of hardwood. This synthesis operation can be performed any number of times each day. Synthesized hardwood can be sold to the market every evening for money, but any remaining logs are cleared by the system every evening. Qiao doesn't care how much money he earns, but as a perfectionist, he hates wasting the logs he worked hard to obtain.

Therefore, you need to help him solve this problem: please arrange the bridge-building plan for the next $n-1$ days so that all islands are mutually reachable after $n-1$ days, and minimize the total number of logs cleared by the system over these $n-1$ days. You only need to output this minimum total number.

Input

The problem contains multiple test cases. The first line contains a single positive integer $T$ representing the number of test cases.

For each test case: The first line contains two positive integers $n$ ($1 \le n \le 10^5$) and $k$ ($1 \le k \le 10^9$), representing the number of islands and the number of logs required to synthesize one piece of hardwood. The second line contains $n$ positive integers, where the $i$-th number is $t_i$ ($0 \le t_i \le 10^9$), representing the number of trees on the $i$-th island every morning.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$, i.e., $\sum n \le 2 \times 10^5$.

Output

Output $T$ lines, each containing one integer representing the corresponding answer.

Examples

Input 1

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

Output 1

1
2

Note

For the second test case in the example, the bridge-building diagram is shown below.

Specifically, one feasible bridge-building plan is:

• Day 1: Connect island 1 and island 5, obtain $3+5$ logs, synthesize 1 piece of hardwood, 1 log remaining.
• Day 2: Connect island 1 and island 3, obtain $3+4$ logs, synthesize 1 piece of hardwood, 0 logs remaining.
• Day 3: Connect island 5 and island 7, obtain $5+2$ logs, synthesize 1 piece of hardwood, 0 logs remaining.
• Day 4: Connect island 5 and island 6, obtain $5+9$ logs, synthesize 2 pieces of hardwood, 0 logs remaining.
• Day 5: Connect island 6 and island 8, obtain $9+6$ logs, synthesize 2 pieces of hardwood, 1 log remaining.
• Day 6: Connect island 8 and island 4, obtain $6+1$ logs, synthesize 1 piece of hardwood, 0 logs remaining.
• Day 7: Connect island 8 and island 2, obtain $6+1$ logs, synthesize 1 piece of hardwood, 0 logs remaining.

Therefore, a total of 2 logs are wasted, and it can be proven that there is no better plan.