#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//#define min(a,b) (a>b?b:a)
//#define max(a,b) (a>b?a:b)
#define mem(a,num) memset(a,num,sizeof(a))
#define inf(a,n) fill(a,a+n,0x3f3f3f3f)

//#pragma comment(linker, "/STACK:102400000,102400000")

int main()
{
    int n,m,T;
    int keep[32];
    keep[0]=1;
    for(int i=1;i<32;++i)keep[i]=keep[i-1]<<1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        int ans=0,tmp;
        if(m>31)m=31;
        for(int i=m;i>=0;--i){
            if(n>=keep[i]){
                tmp=n/keep[i];
                ans+=tmp;
                n-=tmp*keep[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}