#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<ctype.h>
using namespace std;
inline void rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=res*10+(c&15);
    while(c=getchar(),c>47);
}
int T,n,m;
int main(){
    rd(T);
    while(T--){
        rd(n);rd(m);
        int ans=0;
        for(int i=min(30,m);i>=0;--i){
            int k=1<<i;ans+=n/k;n%=k;
        }
        printf("%d\n",ans);
    }
    return 0;
}