# include <bits/stdc++.h>

    //#include <ext/pb_ds/detail/standard_policies.hpp>
    //#include<ext/pb_ds/assoc_container.hpp>
    //#include<ext/pb_ds/tree_policy.hpp>
    //using namespace __gnu_pbds;
    using namespace std;

    #define F               first
    #define S               second
    #define pb              push_back
    #define pp              pop_back()
    #define UB              upper_bound
    #define LB              lower_bound
    #define ui              unsigned int
    #define ll              long long int
    #define ull             unsigned long long int
    #define ld              long double
    #define pii             pair<int,int>
    #define pll             pair<ll,ll>
    #define vi              vector<int>
    #define vll             vector<ll>
    #define vc              vector<char>
    #define vs              vector<string>
    #define vpii            vector<pii>
    #define vpll            vector<pll>
    #define sti             stack<int>
    #define stll            stack<ll>
    #define qi              queue<int>
    #define qll             queue<ll>
    #define sei             set<int>
    #define sell            set<ll>
    #define sec             set<char>
    #define ses             set<string>
    #define pqi             priority_queue<int>
    #define pqgrt           priority_queue<int,vector<int>,greater<int> >
    #define mpii            map<int,int>
    #define mpll            map<ll,ll>
    #define mpsi            map<string,int>
    #define mpis            map<int,string>
    #define mpci            map<char,int>
    #define umpii           unordered_map<int,int>
    #define umpll           unordered_map<ll,ll>
    #define umpsi           unordered_map<string,int>
    #define umpis           unordered_map<int,string>
    #define umpci           unordered_map<char,int>
    #define ump             unordered_map
    #define use             unordered_set
    #define pq              priority_queue

    #define nl                  '\n'
    #define pf                  printf
    #define sfc(a)              scanf("%c",&a)
    #define sfs(a)              scanf("%s",&a)
    #define sfi1(a)             scanf("%d",&a)
    #define sfi2(a,b)           scanf("%d %d",&a,&b)
    #define sfi3(a,b,c)         scanf("%d %d %d",&a,&b,&c)
    #define sfi4(a,b,c,d)       scanf("%d %d %d %d",&a,&b,&c,&d)
    #define sfd1(a)             scanf("%lf",&a)
    #define sfd2(a,b)           scanf("%lf %lf",&a,&b)
    #define sfd3(a,b,c)         scanf("%lf %lf %lf",&a,&b,&c)
    #define sfd4(a,b,c,d)       scanf("%lf %lf %lf %lf",&a,&b,&c,&d)
    #define sfll1(a)            scanf("%lld",&a)
    #define sfll2(a,b)          scanf("%lld %lld",&a,&b)
    #define sfll3(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
    #define sfll4(a,b,c,d)      scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
    #define sfull1(a)           scanf("%llu",&a)
    #define sfull2(a,b)         scanf("%llu %llu",&a,&b)
    #define sfull3(a,b,c)       scanf("%llu %llu %llu",&a,&b,&c)
    #define sfull4(a,b,c,d)     scanf("%llu %llu %llu %llu",&a,&b,&c,&d)

    #define ang(a, b, c)        acos((b*b+c*c-a*a)/(2.0*b*c))
    #define dist(x1,y1,x2,y2)   sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    #define rev(v)              reverse(v.begin(),v.end())
    #define srt(v)              sort(v.begin(),v.end())
    #define grtsrt(v)           sort(v.begin(),v.end(),greater<pll>())
    #define all(v)              v.begin(),v.end()
    #define minv(v)             *min_element(v.begin(),v.end())
    #define maxv(v)             *max_element(v.begin(),v.end())
    #define cntv(v,a)           count(v.begin(),v.end(),a)
    #define one(x)              __builtin_popcount(x)
    #define valid(tx,ty)        tx>=0&&tx<r&&ty>=0&&ty<c
    #define mem(arr,val)        memset(arr,val,sizeof(arr))
    #define Unique(x)           x.erase(unique(x.begin(),x.end()),x.end())
    #define fast                ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
    #define forstl(it,v)        for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
    #define loop(i,n)           for(int i=0;i<n;i++)
    #define loop1(i,n)          for(int i=1;i<=n;i++)
    #define case_print          printf("Case %d: ",t+1)

    template <class T1> void deb(T1 e1){cout<<e1<<endl;}
    template <class T1,class T2> void deb(T1 e1,T2 e2){cout<<e1<<" "<<e2<<endl;}
    template <class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3){cout<<e1<<" "<<e2<<" "<<e3<<endl;}
    template <class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;}
    template <class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;}
    template <class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;}

    template <typename T> T gcd(T a, T b){while (b){T t = a % b;a = b;b = t;}return a;}
    template <typename T> T lcm(T a, T b){return a / gcd(a, b) * b;}
    template <typename T> T gcd(T a, T b, T c){return gcd(gcd(a, b), c);}
    template <typename T> bool isPrime(T x){if (x<=4||x%2==0||x%3==0)return x == 2 || x == 3;for (T i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0;return 1;}
    template <typename T> bool bitcheck(T p,T pos){return (bool)(p&(1<<pos));}
    template <typename T> T biton(T p,T pos){return p=p|(1<<pos);}
    template <typename T> T bitoff(T p,T pos){return p=p&~(1<<pos);}
    template <typename T> ll toint(T s) {ll p;stringstream ss(s); ss>>p; return p;}
    template <typename T> string tostring(T n) {stringstream ss; ss << n; return ss.str();}
    template <typename T> T POW(T b,T p) {T Ans=1; while(p){if(p&1)Ans=(Ans*b);b=(b*b);p>>=1;}return Ans;}
    template <typename T> T BigMod(T b,T p, T mod) {T Ans=1; while(p){if(p&1)Ans=(Ans*b)%mod;b=(b*b)%mod;p>>=1;}return Ans;}
    template <typename T> T ModInverse(T p,T Mod) {return BigMod(p,Mod-2,Mod);}
    //template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    //template <typename T> using ordered_set2 = tree<pair <T, string>, null_type, less<pair <T, string>>, rb_tree_tag, tree_order_statistics_node_update>;
    //ll histogram(ll arr[],ll n){ll top,i=0,sum=0,max_area=0;stack<ll>st;st.push(0);while(i<n){if(st.empty()||arr[st.top()]<=arr[i]) st.push(i++);else{top=st.top();st.pop();if(st.empty())sum=arr[top]*i;else sum=arr[top]*(i-st.top()-1);max_area=max(sum,max_area);}}while(!st.empty()){top=st.top();st.pop();if(st.empty()) sum=arr[top]*i;else sum=arr[top]*(i-st.top()-1);max_area=max(sum,max_area);}return max_area;}
    //ll ext_gcd(ll a,ll b,ll *x,ll *y){if(a==0){*x=0;*y=1;return b;}ll x1,y1;ll gcd = ext_gcd(b%a,a,&x1,&y1);*x=y1-(b/a)*x1;*y=x1;return gcd;}

    const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
    const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
    const int mx        = 1e6+1;
    const int inf       = 0x3f3f3f3f;
    ll mod       = 1e9+7;
    const ld PI         = 2*acos(0.0);
    const ld E          = 2.71828182845904523536;
    const ld eps        = 1e-9;
    //ll fact[2*1000005];
    //void factorial(){fact[0]=1;loop1(i,2*1000005) fact[i]=(fact[i-1]*i)%mod;}
    //ll nCr(ll n,ll r){return (fact[n]*ModInverse(((ll)fact[n-r]*(ll)fact[r])%mod,(ll)mod))%mod;}
    bool mark[mx];vector<ll>prime;
    void sieve(){memset(mark,true,sizeof(mark));for(ll i=3;i<=(ll)sqrt(mx);i+=2){if(mark[i]){for(ll j=i*i;j<=mx;j+=2*i) mark[j]=false;}}prime.push_back(2);for(ll i=3;i<=mx;i+=2) if(mark[i]) prime.push_back(i);}
    ///code start here
    /*int csum[100000+5], csum1[100000+5], a[100000+5], t[100000+5];
    int pre(int r, int l){
        l = (l==0)? l:csum1[l-1];
        r = csum1[r];
        return r-l;
    }*/
    int p[mx];

    int main(){
        int t;
        cin >> t;
        while(t--){
            int n, W;
            cin >> n >> W;
            ll w[n];
            multiset<int> s;
            for(int i=0; i<n; i++){
                cin >> w[i];
                s.insert(w[i]);
            }
            sort(w,w+n);
            ll sum = 0;
            ll temp = W;
            ll h = 1;
            while(s.size()>0){
                auto x = s.upper_bound(temp);
                if(x==s.begin()){
                    temp = W;
                    h++;
                }
                else{
                    ll val = *(--x);
                    temp -= val;
                    s.erase(x);
                }
            }
            cout << h << nl;

        }

    }

### Prompt

Develop a solution in Cpp to the problem described below:

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 <bits/stdc++.h>

    //#include <ext/pb_ds/detail/standard_policies.hpp>
    //#include<ext/pb_ds/assoc_container.hpp>
    //#include<ext/pb_ds/tree_policy.hpp>
    //using namespace __gnu_pbds;
    using namespace std;

    #define F               first
    #define S               second
    #define pb              push_back
    #define pp              pop_back()
    #define UB              upper_bound
    #define LB              lower_bound
    #define ui              unsigned int
    #define ll              long long int
    #define ull             unsigned long long int
    #define ld              long double
    #define pii             pair<int,int>
    #define pll             pair<ll,ll>
    #define vi              vector<int>
    #define vll             vector<ll>
    #define vc              vector<char>
    #define vs              vector<string>
    #define vpii            vector<pii>
    #define vpll            vector<pll>
    #define sti             stack<int>
    #define stll            stack<ll>
    #define qi              queue<int>
    #define qll             queue<ll>
    #define sei             set<int>
    #define sell            set<ll>
    #define sec             set<char>
    #define ses             set<string>
    #define pqi             priority_queue<int>
    #define pqgrt           priority_queue<int,vector<int>,greater<int> >
    #define mpii            map<int,int>
    #define mpll            map<ll,ll>
    #define mpsi            map<string,int>
    #define mpis            map<int,string>
    #define mpci            map<char,int>
    #define umpii           unordered_map<int,int>
    #define umpll           unordered_map<ll,ll>
    #define umpsi           unordered_map<string,int>
    #define umpis           unordered_map<int,string>
    #define umpci           unordered_map<char,int>
    #define ump             unordered_map
    #define use             unordered_set
    #define pq              priority_queue

    #define nl                  '\n'
    #define pf                  printf
    #define sfc(a)              scanf("%c",&a)
    #define sfs(a)              scanf("%s",&a)
    #define sfi1(a)             scanf("%d",&a)
    #define sfi2(a,b)           scanf("%d %d",&a,&b)
    #define sfi3(a,b,c)         scanf("%d %d %d",&a,&b,&c)
    #define sfi4(a,b,c,d)       scanf("%d %d %d %d",&a,&b,&c,&d)
    #define sfd1(a)             scanf("%lf",&a)
    #define sfd2(a,b)           scanf("%lf %lf",&a,&b)
    #define sfd3(a,b,c)         scanf("%lf %lf %lf",&a,&b,&c)
    #define sfd4(a,b,c,d)       scanf("%lf %lf %lf %lf",&a,&b,&c,&d)
    #define sfll1(a)            scanf("%lld",&a)
    #define sfll2(a,b)          scanf("%lld %lld",&a,&b)
    #define sfll3(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
    #define sfll4(a,b,c,d)      scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
    #define sfull1(a)           scanf("%llu",&a)
    #define sfull2(a,b)         scanf("%llu %llu",&a,&b)
    #define sfull3(a,b,c)       scanf("%llu %llu %llu",&a,&b,&c)
    #define sfull4(a,b,c,d)     scanf("%llu %llu %llu %llu",&a,&b,&c,&d)

    #define ang(a, b, c)        acos((b*b+c*c-a*a)/(2.0*b*c))
    #define dist(x1,y1,x2,y2)   sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    #define rev(v)              reverse(v.begin(),v.end())
    #define srt(v)              sort(v.begin(),v.end())
    #define grtsrt(v)           sort(v.begin(),v.end(),greater<pll>())
    #define all(v)              v.begin(),v.end()
    #define minv(v)             *min_element(v.begin(),v.end())
    #define maxv(v)             *max_element(v.begin(),v.end())
    #define cntv(v,a)           count(v.begin(),v.end(),a)
    #define one(x)              __builtin_popcount(x)
    #define valid(tx,ty)        tx>=0&&tx<r&&ty>=0&&ty<c
    #define mem(arr,val)        memset(arr,val,sizeof(arr))
    #define Unique(x)           x.erase(unique(x.begin(),x.end()),x.end())
    #define fast                ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
    #define forstl(it,v)        for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
    #define loop(i,n)           for(int i=0;i<n;i++)
    #define loop1(i,n)          for(int i=1;i<=n;i++)
    #define case_print          printf("Case %d: ",t+1)

    template <class T1> void deb(T1 e1){cout<<e1<<endl;}
    template <class T1,class T2> void deb(T1 e1,T2 e2){cout<<e1<<" "<<e2<<endl;}
    template <class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3){cout<<e1<<" "<<e2<<" "<<e3<<endl;}
    template <class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;}
    template <class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;}
    template <class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;}

    template <typename T> T gcd(T a, T b){while (b){T t = a % b;a = b;b = t;}return a;}
    template <typename T> T lcm(T a, T b){return a / gcd(a, b) * b;}
    template <typename T> T gcd(T a, T b, T c){return gcd(gcd(a, b), c);}
    template <typename T> bool isPrime(T x){if (x<=4||x%2==0||x%3==0)return x == 2 || x == 3;for (T i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0;return 1;}
    template <typename T> bool bitcheck(T p,T pos){return (bool)(p&(1<<pos));}
    template <typename T> T biton(T p,T pos){return p=p|(1<<pos);}
    template <typename T> T bitoff(T p,T pos){return p=p&~(1<<pos);}
    template <typename T> ll toint(T s) {ll p;stringstream ss(s); ss>>p; return p;}
    template <typename T> string tostring(T n) {stringstream ss; ss << n; return ss.str();}
    template <typename T> T POW(T b,T p) {T Ans=1; while(p){if(p&1)Ans=(Ans*b);b=(b*b);p>>=1;}return Ans;}
    template <typename T> T BigMod(T b,T p, T mod) {T Ans=1; while(p){if(p&1)Ans=(Ans*b)%mod;b=(b*b)%mod;p>>=1;}return Ans;}
    template <typename T> T ModInverse(T p,T Mod) {return BigMod(p,Mod-2,Mod);}
    //template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    //template <typename T> using ordered_set2 = tree<pair <T, string>, null_type, less<pair <T, string>>, rb_tree_tag, tree_order_statistics_node_update>;
    //ll histogram(ll arr[],ll n){ll top,i=0,sum=0,max_area=0;stack<ll>st;st.push(0);while(i<n){if(st.empty()||arr[st.top()]<=arr[i]) st.push(i++);else{top=st.top();st.pop();if(st.empty())sum=arr[top]*i;else sum=arr[top]*(i-st.top()-1);max_area=max(sum,max_area);}}while(!st.empty()){top=st.top();st.pop();if(st.empty()) sum=arr[top]*i;else sum=arr[top]*(i-st.top()-1);max_area=max(sum,max_area);}return max_area;}
    //ll ext_gcd(ll a,ll b,ll *x,ll *y){if(a==0){*x=0;*y=1;return b;}ll x1,y1;ll gcd = ext_gcd(b%a,a,&x1,&y1);*x=y1-(b/a)*x1;*y=x1;return gcd;}

    const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
    const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
    const int mx        = 1e6+1;
    const int inf       = 0x3f3f3f3f;
    ll mod       = 1e9+7;
    const ld PI         = 2*acos(0.0);
    const ld E          = 2.71828182845904523536;
    const ld eps        = 1e-9;
    //ll fact[2*1000005];
    //void factorial(){fact[0]=1;loop1(i,2*1000005) fact[i]=(fact[i-1]*i)%mod;}
    //ll nCr(ll n,ll r){return (fact[n]*ModInverse(((ll)fact[n-r]*(ll)fact[r])%mod,(ll)mod))%mod;}
    bool mark[mx];vector<ll>prime;
    void sieve(){memset(mark,true,sizeof(mark));for(ll i=3;i<=(ll)sqrt(mx);i+=2){if(mark[i]){for(ll j=i*i;j<=mx;j+=2*i) mark[j]=false;}}prime.push_back(2);for(ll i=3;i<=mx;i+=2) if(mark[i]) prime.push_back(i);}
    ///code start here
    /*int csum[100000+5], csum1[100000+5], a[100000+5], t[100000+5];
    int pre(int r, int l){
        l = (l==0)? l:csum1[l-1];
        r = csum1[r];
        return r-l;
    }*/
    int p[mx];

    int main(){
        int t;
        cin >> t;
        while(t--){
            int n, W;
            cin >> n >> W;
            ll w[n];
            multiset<int> s;
            for(int i=0; i<n; i++){
                cin >> w[i];
                s.insert(w[i]);
            }
            sort(w,w+n);
            ll sum = 0;
            ll temp = W;
            ll h = 1;
            while(s.size()>0){
                auto x = s.upper_bound(temp);
                if(x==s.begin()){
                    temp = W;
                    h++;
                }
                else{
                    ll val = *(--x);
                    temp -= val;
                    s.erase(x);
                }
            }
            cout << h << nl;

        }

    }

```