题目描述

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

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

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

输入格式

第一行一个整数 $n$。

接下来 $n$ 行每行两个数 $x$ 和 $k$ ($k$ <= $x$的二进制 中 1的个数)。

输出格式

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

样例

2
5 2
7 2

4
2

2
8 1
6 1

8
2

数据范围