#include <iostream>
using namespace std;
#define LL long long
LL fact[100];
int T;LL n,m; 
int main(){
    cin>>T;
    fact[0]=1;
    for(int i=1;i<=50;i++) fact[i]=fact[i-1]*2;
    //cout<<fact[45]<<endl;
    while(T--){
        scanf("%I64d%I64d",&n,&m);
        LL ans=0;int cnt;
        if(m>49) m=45;
        
        for(int i=m;i>=0;i--){
            if(fact[i]<=n){
                cnt=i;
                break;
            }
        }
        ans=n/fact[cnt];
        n=n%fact[cnt];
        //cout<<cnt<<endl;
        while(n!=0){
            n-=fact[cnt];
            if(n<0){
                n+=fact[cnt];
                cnt--;
                continue;
            }
            
            ans++;
            //cout<<ans<<endl;
        }
        printf("%d\n",ans);
        
        
    }
    
    
    return 0;
}


/*
输入样例
 10
1 2
3 2
5 2
10 2
10 3
10 4
13 5
20 4
11 11
12 3
输出样例
 1
2
2
3
2
2
3
2
3
2



*/