#include<stdio.h>
#include<algorithm>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int main ()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int sum=0;
        //m++;
        while(m--&&n>0)
        {
            if(n%2==1)
            {
                sum++;
            }
            n/=2;
        }
        sum+=n;
        printf("%d\n",sum);
    }
}