#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a[1000];
int main(){
    int tt;
    scanf("%d",&tt);
    while(tt--){
        long long n,m;
        scanf("%I64d%I64d",&n,&m);
        int tot=0,cur=1;
        while(cur<=n){
            a[tot++]=cur;
            cur=cur*2;
        }
        long long ans=0;
        for(int i=min(m,1LL*tot-1);i>=0;i--){
            ans+=n/a[i];
            n%=a[i];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}