Minimum Trips on a Conveyor Belt

You are given n bags with respective weights and a conveyor belt with a maximum capacity c per trip. In each trip, the bags are considered in descending order and you pick a contiguous prefix of bags (starting from the heaviest) such that each bag fits into the remaining capacity. Once you find a bag that does not fit at that position, you stop picking for that trip and schedule the next trip with the remaining bags.

Objective: Compute the minimum number of trips required to transport all the bags.

Note: The bags are processed in sorted order (descending) and only a contiguous sequence (starting from the first bag) that fits into the remaining capacity is loaded in each trip. This process repeats until all bags are transported.

The problem can be formulated using the following equation for each trip:

[ \text{Let } r = c - \sum_{i=1}^{k} w_i \geq 0 \quad \text{for the largest } k \text{ such that } w_i \leq r \text{ for } 1 \leq i \leq k. ]

Then, the total number of trips is the number of iterations needed to remove all bags.

inputFormat

The input is given on standard input (stdin) and has the following format:

T
n1 c1
w1,1 w1,2 ... w1,n1
n2 c2
w2,1 w2,2 ... w2,n2
... 
nT cT
wT,1 wT,2 ... wT,nT

Here, T is the number of test cases. For each test case, the first line contains two integers: the number of bags n and the maximum capacity c of the conveyor. The following line contains n integers representing the weights of the bags.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of trips needed to transport all the bags, using the described greedy approach. The output should be written to standard output (stdout).

## sample

3
5 10
2 3 5 7 1
4 6
3 1 4 2
7 15
5 10 5 5 5 5 5

3
2
3

</p>