#include<cstdio>
int main(){
    int T;
    scanf("%d", &T);
    for(int ca = 0; ca < T; ca++){
        int n, m;
        scanf("%d%d", &n, &m);
        int k = 0;
        int ans = 0;
        while( (1 << (k + 1)) <= n && k + 1 <= m) k++; 
        while(k >= 0) ans += n / (1 << k), n %= (1 << k), k--;
        printf("%d\n", ans);
    }
    return 0;
}