#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
 //   freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    int T,i,j,n,m,ans;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);ans=0;
        for (i=0;(1<<i)<=n;i++);i--;m=min(i,m);
        for (j=m;j>=0;j--)
        {
            ans+=n/(1<<j);n%=(1<<j);
        }
        printf("%d\n",ans);
    }
    
    return 0;
}