#include <iostream> 
#include <string> 
#include <set> 
#include <map> 
#include <stack> 
#include <queue> 
#include <vector> 
#include <utility> 
#include <iomanip> 
#include <sstream> 
#include <bitset> 
#include <cstdlib> 
#include <iterator> 
#include <algorithm> 
#include <array>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <cstdio> 
#include <cctype> 
#include <cmath>
#include <memory>
#include <numeric>
#include <ctime> 
using namespace std;
#define ll long long

const int MAXN = 2e5;
int widths[MAXN], n, w;

bool check(int x) {
	priority_queue<int> t;
	for(int i=0; i<x; i++) {
		t.push(w);
	}
	for(int i=0; i<n; i++) {
		int big = t.top();
		t.pop();
		if(big < widths[i]) return false;
		t.push(big-widths[i]);
	}
	return true;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> w;
		for(int i=0; i<n; i++) {
			cin >> widths[i];
		}
		sort(widths, widths+n, greater<int>());
		int l = 1, r = n+1;
		while(l < r) {
			int mid = (l+r)/2;
			if(!check(mid)) {
				l = mid+1;
			}
			else {
				r = mid;
			}
		}
		cout << r << endl;
		for(int i=0; i<n; i++) {
			widths[i] = 0;
		}
	}
}





### Prompt

Your challenge is to write a Cpp solution to the following problem:

You are given n rectangles, each of height 1. Each rectangle's width is a power of 2 (i. e. it can be represented as 2^x for some non-negative integer x). 

You are also given a two-dimensional box of width W. Note that W may or may not be a power of 2. Moreover, W is at least as large as the width of the largest rectangle.

You have to find the smallest height of this box, such that it is able to fit all the given rectangles. It is allowed to have some empty space left in this box after fitting all the rectangles.

You cannot rotate the given rectangles to make them fit into the box. Moreover, any two distinct rectangles must not overlap, i. e., any two distinct rectangles must have zero intersection area.

See notes for visual explanation of sample input.

Input

The first line of input contains one integer t (1 ≤ t ≤ 5 ⋅ 10^3) — the number of test cases. Each test case consists of two lines.

For each test case:

  * the first line contains two integers n (1 ≤ n ≤ 10^5) and W (1 ≤ W ≤ 10^9);
  * the second line contains n integers w_1, w_2, ..., w_n (1 ≤ w_i ≤ 10^6), where w_i is the width of the i-th rectangle. Each w_i is a power of 2;
  * additionally, max_{i=1}^{n} w_i ≤ W. 



The sum of n over all test cases does not exceed 10^5.

Output

Output t integers. The i-th integer should be equal to the answer to the i-th test case — the smallest height of the box.

Example

Input


2
5 16
1 2 8 4 8
6 10
2 8 8 2 2 8


Output


2
3

Note

For the first test case in the sample input, the following figure shows one way to fit the given five rectangles into the 2D box with minimum height:

<image>

In the figure above, the number inside each rectangle is its width. The width of the 2D box is 16 (indicated with arrow below). The minimum height required for the 2D box in this case is 2 (indicated on the left).

In the second test case, you can have a minimum height of three by keeping two blocks (one each of widths eight and two) on each of the three levels.

### Response

```cpp
#include <iostream> 
#include <string> 
#include <set> 
#include <map> 
#include <stack> 
#include <queue> 
#include <vector> 
#include <utility> 
#include <iomanip> 
#include <sstream> 
#include <bitset> 
#include <cstdlib> 
#include <iterator> 
#include <algorithm> 
#include <array>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <cstdio> 
#include <cctype> 
#include <cmath>
#include <memory>
#include <numeric>
#include <ctime> 
using namespace std;
#define ll long long

const int MAXN = 2e5;
int widths[MAXN], n, w;

bool check(int x) {
	priority_queue<int> t;
	for(int i=0; i<x; i++) {
		t.push(w);
	}
	for(int i=0; i<n; i++) {
		int big = t.top();
		t.pop();
		if(big < widths[i]) return false;
		t.push(big-widths[i]);
	}
	return true;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> w;
		for(int i=0; i<n; i++) {
			cin >> widths[i];
		}
		sort(widths, widths+n, greater<int>());
		int l = 1, r = n+1;
		while(l < r) {
			int mid = (l+r)/2;
			if(!check(mid)) {
				l = mid+1;
			}
			else {
				r = mid;
			}
		}
		cout << r << endl;
		for(int i=0; i<n; i++) {
			widths[i] = 0;
		}
	}
}





```