#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
using namespace std;
int T,n,m;
void doing()
{
    scanf("%d%d",&n,&m);
    int flag=1,i,ans=0;
    for (i=1;i<=m;i++) if (flag<=n) flag*=2; else break;
    if (flag>n) flag/=2;
    //cout<<flag<<endl;
    //cout<<n/flag<<endl;
    while (n>0)
    {
        //cout<<n<<" "<<flag<<endl;
        if (flag==0) break;
        int t=n/flag;
        ans=ans+t;
        n=n-t*flag;
        flag/=2;
    }
    printf("%d\n",ans);
 }
int main()
{
    scanf("%d",&T);
    int i;
    for (i=1;i<=T;i++) doing();
    return 0;
 }