#include<stdio.h>
#include <iostream>
using namespace std;
int get(int x)
{
    int hig=0;
    while(x)
    {
        //if(x&1) cnt++;
        x>>=1;
        hig++;
    }
    return hig;
}
int getcnt(int x)
{
    int cnt=0;
    while(x)
    {
        if(x&1) cnt++;
        x>>=1;
        //hig++;
    }
    return cnt;
}
int xx[]={1};

int main()
{
    for(int i=1;i<32;i++)
    {
        xx[i] = xx[i-1]*2;
    }

//    int cnt=0,hig=0;
  //  get(3,cnt,hig);
    //cout<<cnt<<" "<<hig<<endl;
    int t,a,b;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&a,&b);
        int cnt=0,hig=0;
        hig = get(a);
        if(b>30) b=30;
        if(b==0)
        {
            printf("%d\n",a);
        }
        else if(a==xx[b])
        {
            printf("1\n");
        }
        else if(hig<b+1)
        {
            cnt = getcnt(a);
            printf("%d\n",cnt);
        }
        else
        {
            int div = a/xx[b];
            int mod = a%xx[b];
            int ans = div+getcnt(mod);
            printf("%d\n",ans);
        }
    }
}