E. Epsilon Estuary
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

Recently, Colin got addicted to playing a tactics puzzle RPG: Super Algebrawl. In the game, Colin transforms into a boar king with magical mathematical powers! He is on a quest for glory, slaying the horrible monsters that plague the animal realm. Every encounter is a puzzle to be solved with logic and simple algebra!

Just now, Colin came to the next battlefield: Epsilon Estuary. The slimes are the rulers here, and they have a disgusting splitting skill - "SPLASH": once it is injured, assuming its remaining health is $$$x$$$, it will immediately split into two slimes with health $$$\lfloor x/2\rfloor$$$ and $$$\lceil x/2 \rceil$$$ respectively, and the new slimes can continue to use this skill if they are injured in the future. A slime with health $$$0$$$ will die immediately.

However, our challenger Colin happens to have the best weapon against them: the "SHOCK" magic scroll! Specifically, every time Colin uses the shock magic scroll, it will inflict $$$y$$$ damage to every monster. If a monster's health does not exceed $$$y$$$ before Colin uses the magic scroll, it will die immediately after Colin uses the magic scroll.

The image above shows an example: assuming $$$y=5$$$, and there are two slimes on the field with health values $$$x_1=25,\ x_2=8$$$. After Colin used the scroll once, their health became $$$x_1'=20,\ x_2'=3$$$ respectively. Then they split immediately. The first slime split into two slimes with health $$$10$$$ and $$$10$$$ respectively; the second slime split into two slimes with health $$$2$$$ and $$$1$$$ respectively.

Colin's magic scroll can be used any number of times, so this is destined to be a one-way killing. But clicking the mouse repeatedly is too tiring, so Colin would like you to calculate, given the initial status of the slimes on the field, how many times he needs to use the scroll at least to ensure that all monsters on the field are killed?

Input

The first line contains a single integer $$$T\ (1\le T\le 10^5)$$$, representing the number of test cases.

For each test case:

  • The first line contains two integers $$$n,y\ (1\le n\le 10^5, 1\le y\le 10^{18})$$$, representing the number of slimes on the battlefield and the damage that can be dealt to each slime by using the magic scroll once.
  • The second line contains $$$n$$$ integers $$$x_1,x_2,\dots,x_n\ (1\le x_i\le 10^{18})$$$, representing the initial health of each slime on the battlefield.

It's guaranteed that the sum of $$$n$$$ over all the test cases will not exceed $$$10^6$$$.

Output

Output $$$T$$$ lines, the $$$i$$$-th line contains a single integer, representing the answer for the $$$i$$$-th test case.

Example
Input
2
2 5
25 8
1 1
100
Output
3
7
Note

For the first test case, the changes in health of the slimes on the field are: $$$$$$ \{25,8\}\to\{10,10,2,1\}\to\{3,2,3,2\}\to\emptyset $$$$$$