题目描述
小峰最近对能整除2的数字特别感兴趣。对于一个能恰好整除 k(k为正整数)个2的整数x，意味着x能整除 k 个2但不能整除 k+1 个2。
例如4恰好能整除2个2，8恰好能整除3个2，24恰好能整除3个2。
小峰想快速地多次查询对于 1~n 的所有整数，有多少个整数能恰好整除 k 个2。
但小峰不会，所以想求助编程水平好的你来帮忙解决。
输入描述
第一行输入一个正整数 t，表示有t个测试样例。
随后 t 行，每行输入两个正整数 n,k，两个整数之间以空格间隔，含义如上。
输出描述
输出 t 行，对于每一行输出一个整数，即对于 1~n 的所有整数，有多少个整数能恰好整除 k 个2。
样例输入
6 6 2 30 3 1 2 64 4 128 3 256 4
样例输出
1 2 0 2 8 8
样例解释：
第一次询问，1~6中能恰好整除2个2的有4，共1个
第二次询问，1~30中能恰好整除3个2的有8，24，共2个
第三次询问，1~1中没有能恰好整除2个2的数
第四次询问，1~64中能恰好整除4个2的有16，48，共2个
第五次询问，1~128中能恰好整除3个2的有8，24，40，56，72，88，104，120，共8个
第六次询问，1~256中能恰好整除4个2的有16，48，80，112，144，176，208，240，共8个
数据范围：
1 <= t <= 2e5
对于30%的数据： 1 <= n <= 100, 1 <= k <= 29;
对于50%的数据： 1 <= n <= 2e5, 1 <= k <= 29;
对于100%的数据： 1 <= n <= 1e9, 1 <= k <= 29;
