#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define INF 0X3F3F3F3F
#define MOD 1000000007
#define N 100010
#define FF(i,a,b) for(int i=a;i<=b;++i)
#define RR(i,a,b) for(int i=a;i>=b;--i)
#define FJ(i,a,b) for(int i=a;i<b;++i)
#define SC(x) scanf("%d",&x)
#define SCC(x,y) scanf("%d%d",&x,&y)
#define SCCC(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define SS(x) scanf("%s",x)
#define PR(x) printf("%d\n",x)
#define CL(a,b) memset(a,b,sizeof(a))
#define FD T&q=fd[rt],&ql=fd[rt<<1],&qr=fd[rt<<1|1]
#define MID int mid=((L+R)>>1)
#define lson rt<<1, L, (L + R)>>1
#define rson rt<<1|1,  ((L + R)>>1) + 1, R
#define EPS 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define PB push_back
#define SI size()
#define PII pair<int,int>
#define MP make_pair
#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int main(){
#ifndef ONLINE_JUDGE
IN;
#endif
int _,a[100],n,m;
int po[50];
po[0]=1;
FF(i,1,30)po[i]=po[i-1]*2;
for(SC(_);_--;){
    SCC(n,m);
    CL(a,0);
    m=min(30,m);
    for(int i=m;i>=0;--i){
        a[i]=n/po[i];
        n-=a[i]*po[i];
    }
    int ans=0;
    FF(i,0,m)ans+=a[i];
    printf("%d\n",ans);
}
return 0;
}