#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std;
int main()
{
    ll n,m,T;
    ll base[33];
    base[0]=1;
    for(int i=1;i<33;i++)
        base[i]=2*base[i-1];
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        ll ans=0;
        for(ll k=min(m,32ll);k>=0;k--)
        {
            if(base[k]<=n)
            {
                ans+=n/base[k];
                n=n%base[k];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}