#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vec;
typedef priority_queue<int> pq;
#define pb push_back
#define ph push
#define fi first
#define se second
inline void Max(int &a,int b){if(a<b)a=b;}
inline void Min(int &a,int b){if(a>b||a==-1)a=b;}
template<class T>void rd(T &a){
    a=0;char c;
    while(c=getchar(),!isdigit(c));
    do a=a*10+(c^48);
        while(c=getchar(),isdigit(c));
}
template<class T>void nt(T x){
    if(!x)return;
    nt(x/10);
    putchar(48+x%10);
}
template<class T>void pt(T x){
    if(!x)putchar('0');
    else nt(x);
}
inline ll Mod_Pow(int x,int a){
    ll res=1;
    for(int i=0;(1ll<<i)<=a;++i){
        if(a&1<<i)res=1ll*res*x;
        x=1ll*x*x;
    }
    return res;
}
inline void gao(){
    int n,m;
    rd(n),rd(m);
    ll k=1;
    for(int i=1;i<=m;++i){
        k<<=1;
        if(k>n){m=i-1;break;}
    }
    ll ans=0;
    for(int i=m;~i;--i){
        k=Mod_Pow(2,i);
        int w=n/k;
        ans+=w;
        n-=1ll*w*k;
        k>>=1;
    }
    pt(ans);
    putchar('\n');
}
int main(){
    int _;
    for(cin>>_;_--;)gao();
}