#include #include #include #include #include #include #include using namespace std; const int N=100005; int main() { int i,j,k,n; long long m[56]; m[0]=1; int T; for(i=1;i<=50;i++) m[i]=2*m[i-1]; scanf("%d",&T); long long a,b; while(T--) { cin>>a>>b; long long ans=0; for(i=min(b,(long long)50);i>=0;i--) { ans+=a/m[i]; a%=m[i]; } cout<