Brandon likes to detonate fireworks. However, fireworks leave behind a lot of trash. Brandon has adjusted the Trash Push to clear out arbitrary trash, but the Trash Push is extremely tiring to perform after every firework detonation. Brandon wonders if some of his Trash Pushes are unnecessary.

We will model how Brandon takes out the trash as follows - he has infinitely many trash cans that can store up to ~K~ units of trash. Over the course of ~N~ days, Brandon will detonate some fireworks. On day ~i~, Brandon will accumulate ~a_i~ units of trash. When Brandon executes a Trash Push, he takes all the trash he has and pushes it into a trash can. As before, the trash that overflows will automatically enter another trash can. A Trash Push is unnecessary if, after executing it, no trash can is completely full of trash. Brandon can execute a Trash Push at any time, as long as he has at least one unit of trash to push. After executing a Trash Push, Brandon takes all trash cans that have trash in them and takes them outside. They are emptied overnight and Brandon brings them back in the next day.

Given the amount of trash Brandon will generate over the next ~N~ days, compute the maximum number of Trash Pushes Brandon can perform, given that none of them are unnecessary.

Constraints

~1 \le T \le 10^4~

~1 \le N \le 10^6~

~1 \le K, a_i \le 10^9~

The sum of all ~N~ in an input file will not exceed ~10^6~.

Input Specification

The first line contains a single positive integer ~T~, the number of test cases.

~T~ test cases follow.

Each test case starts with a line containing two space-separated positive integers, ~N~ and ~K~. The next line contains ~N~ space-separated integers, the ~a_i~ values.

Test cases are independent - at the beginning of a test case, you may assume Brandon always has zero trash.

Output Specification

Output ~T~ lines. On the ~i~th line, output the maximum number of Trash Pushes Brandon can perform, given that none of them is unnecessary for the ~i~th test case.

Sample Input

3
3 1
1 2 3
3 3
1 2 3
3 39
31 41 59

Sample Output

3
2
2