Minimum Number of Boxes

You are given T test cases. In each test case, you are provided with a number of items n, a maximum weight capacity w for each box, and a list of item weights. Your task is to determine the minimum number of boxes needed to pack all the items, such that the total weight in each box does not exceed w.

In other words, given item weights \(a_1, a_2, \ldots, a_n\) and a box capacity \(w\), you need to partition the items into the minimum number of groups so that for every group the sum of weights does not exceed \(w\). You may assume that it is always possible to pack an item into a new box even if its weight exceeds w (i.e. a box may have negative remaining capacity after packing such an item), as illustrated by the sample test cases.

Note: The items can be rearranged arbitrarily to achieve an optimal or near‐optimal packing solution. A greedy strategy that sorts items in descending order and places each item into the first box that can accommodate it is acceptable for this problem.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), representing the number of test cases. For each test case, the first line contains two integers (n) and (w) representing the number of items and the maximum weight capacity of a box respectively. The next line contains (n) space-separated integers denoting the weights of the items.

outputFormat

For each test case, output a single line containing the minimum number of boxes required to pack all items. The output should be written to standard output (stdout).## sample

6
5 10
1 8 3 5 12
4 20
15 10 5 7
1 10
5
3 5
1 1 1
4 50
25 25 25 25
3 100
100 100 100

3
2
1
1
2
3