二进制中的第k个1的值

题目描述:

给定 n 个询问，每次询问内容是：

在正整数x中，从低位开始，第 k 个 1 的值对应是多少。

比如说，在5中，第二个 1 对应的值为 4，因为 5 的二进制是 101，第二个 1 对应的值是 100，也就是 4。

输入格式:

第一行一个整数 n。

接下来 n 行每行两个数 x 和 k (  k 不一定小于等于 x的二进制中1的个数 )。

输出格式:

对于每个询问，输出对应的答案，每个答案独占一行。

数据范围:

测试点30%， 满足 1≤n≤100。

测试点60%， 满足 1≤n≤1000。

测试点100%， 满足 1≤n≤1e5 ，0≤x ≤1e9 ,  k 不一定小于等于 x的二进制中1的个数。

样例输入:

样例1：
2
5 2
7 2

样例2：
2
8 1
6 1

样例输出:

样例1：
4
2

样例2：
8
2

提示:

k大于x的二进制中1的个数，输出0。

时间限制: 1000ms
空间限制: 256MB

---