Harry and Hermione - 2

Limits 1s, 512 MB

[1 and 2 are completely different problems. Consider reading both.]

The monsters are back again. Harry and Hermione are fighting the monsters. There are $n$ monsters, and their health point is described by an array $h$ consisting of $n$ positive integers. A monster is dead when its health point becomes non-positive ( $\le 0$ ).

To fight these monsters, Harry knows a spell which can be casted over a single monster and has power $x$ . On the other hand, Hermione knows a spell which can be casted over multiple monsters and has power $y$ .

Initially, $y = 1$ and $x$ is given in the input.

Starting from day $1$ , the following happens in each day in the order mentioned:

1. Harry selects a monster, and deals $x$ damage to that monster. [It is possible to select a monster which is already dead]

2. Hermione casts her spell over all the other monsters (excluding the one Harry selected) and deals $y$ damage to each of these monsters.

3. $x$ is increased by $1$ .

4. $y$ is increased by $1$ .

If Harry and Hermione fight optimally, calculate the minimum number of days needed to kill all the monsters.

Input

The first line of the input contains a single integer $t (1\le t \le 10000)$ — the number of test cases.

Each test case consists of two lines. The first line contains two integers $n$ and $x$ $(1 \le n \le 2 \times 10^5 ; 2 \le x \le 10^9)$ — the number of monsters and initial power of Harrys spell respectively.

The second line contains $n$ integers $h_1,h_2,\ldots,h_n$ $(1 \le h_i \le 10^9)$ — initial health point of each monster.

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

Output

For each test case, print a single integer — minimum number of days needed to kill all the monsters.

Sample

Input	Output
4 4 7 2 2 8 10 3 6 3 3 9 2 3 3 10 1 5 2	3 2 3 1
Explanation of test case $1$ : Starting of day $1$ : $h = [2,2,8,10]$ , $x = 7$ , $y = 1$ 1. Select $4th$ monster, decrease its health by $x=7$ . $h = [2,2,8,3]$ . 2. Decrease health of each monster by $y=1$ , excluding the $4th$ monster. $h = [1,1,7,3]$ . 3. $x = 8$ 4. $y = 2$ Starting of day $2$ : $h = [1,1,7,3]$ , $x = 8$ , $y = 2$ 1. Select $3rd$ monster. $h = [1,1, -1,3]$ . 2. Decrease health of each monster by $y=2$ , excluding the $3rd$ monster. $h = [-1, -1, -1,1]$ . 3. $x = 9$ 4. $y = 3$ Starting of day $3$ : $h = [-1, -1, -1,1]$ , $x = 9$ , $y = 3$ 1. Select $1st$ monster $h = [-10, -1, -1,1]$ . 2. Decrease health of each monster by $y=3$ , excluding the $1st$ monster. $h = [-10, -4, -4, -2]$ . 3. $x = 10$ 4. $y = 4$ All the monsters are dead after $3$ days.

Input

Output

Explanation of test case $1$ :

Starting of day $1$ : $h = [2,2,8,10]$ , $x = 7$ , $y = 1$

1. Select $4th$ monster, decrease its health by $x=7$ . $h = [2,2,8,3]$ .

2. Decrease health of each monster by $y=1$ , excluding the $4th$ monster. $h = [1,1,7,3]$ .

3. $x = 8$

4. $y = 2$

Starting of day $2$ : $h = [1,1,7,3]$ , $x = 8$ , $y = 2$

1. Select $3rd$ monster. $h = [1,1, -1,3]$ .

2. Decrease health of each monster by $y=2$ , excluding the $3rd$ monster. $h = [-1, -1, -1,1]$ .

3. $x = 9$

4. $y = 3$

Starting of day $3$ : $h = [-1, -1, -1,1]$ , $x = 9$ , $y = 3$

1. Select $1st$ monster $h = [-10, -1, -1,1]$ .

2. Decrease health of each monster by $y=3$ , excluding the $1st$ monster. $h = [-10, -4, -4, -2]$ .

3. $x = 10$

4. $y = 4$

All the monsters are dead after $3$ days.