#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
int main(){
    int _;scanf("%d",&_);
    int n,m;
    while(_--){
        scanf("%d%d",&n,&m);
        int ret=0;
        for(int i=min(m,30);i>=0;i--){
            ret+=n/(1<<i);
            n%=(1<<i);
        }
        printf("%d\n",ret);
    }
    return 0;
}