#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int main(){
    int T,i,n,m;
    scanf("%d ",&T);
    while(T--&&scanf("%d %d",&n,&m)){
        int ans=0;
        for(i=min(31,m);i>=0;i--)
            ans+=(n/(1<<i)),n%=1<<i;
        printf("%d\n",ans);
    }
}