#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
void solve() {
    int t=n,j=0;
    while (t) {
        j++;
        t>>=1;
    }
    j--;
    int ans;
    if (j<=m) ans=0;
    else {
        ans=n/(1<<m);
        n-=ans*(1<<m);
    }
    while (n) {
        if (n&1) ans++;
        n>>=1;
    }
    printf("%d\n",ans);
}
int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        solve();
    }
    return 0;
}