#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100005
#define pop_back pp
#define push_back pb
#define veci vector<int>
#define pii pair<int,int>
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
int T,n,m;
ll f[60];
void Rd(int &res){
    res=0;char c;
    while(c=getchar(),!isdigit(c));
    do res=res*10+(c&15);
        while(c=getchar(),isdigit(c));
}
void Input(){
    scanf("%d%d",&n,&m);
}
void Solve(){
    int res=n,ans=0;
    for(int i=min(40,m);i>=0;i--){
        while(f[i]<=res){
            res-=f[i];
            ans++;
        }
    }
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&T);
    f[0]=1;
    for(int i=1;i<60;i++)f[i]=f[i-1]*2;
    for(;T--;){
        Input();
        Solve();
    }
    return 0;
}