#include <iostream>
#include <stdio.h>

using namespace std;

int t , n , m;

int main()
{
    cin >> t;
    while( t-- )
    {
        scanf( "%d %d" , &n , &m );
        int cnt = 0;
        for( register int i = 0 ; ( 1 << i ) <= n ; i++ )
        {
            if( i >= m )
            {
                cnt += n >> m;
                break;
            }
            if( n & ( 1 << i ) )
                cnt++;
        }
        printf( "%d\n" , cnt );
    }
    return 0;
}