#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<iomanip>
#define eps 1e-8
#define ms(a) memset(a,0,sizeof(a))
#define N 10005
#define M 100000007
#define INF 2e9+7
#define LOOK cout<<"LOOK\n"
using namespace std;
long long mul[N];

void init(){
    mul[0]=1;
    for(int i=1;i<64;++i)
        mul[i]=mul[i-1]*2;
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;++cas){
        long long ans=0,n,m;
        scanf("%I64d%I64d",&n,&m);
        for(int i=min(32LL,m);n;--i){
            if(n>=mul[i]){
                ans+=n/mul[i];
                n-=n/mul[i]*mul[i];
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}
/*
*/