#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
int s=0,t;
int mm;
mm=min(m,32);
t=pow(2,mm);
for(;t;){
if(t<=n){
int x;
x=n/t;
s+=x;
n-=x*t;
t/=2;
}
else t/=2;
}
printf("%d\n",s);
}
return 0;
}
