大桥高中放学后,龙寺递给大河一个正整数 $$$n$$$ 并设置了一个简单的挑战。
他们将精确地进行 $$$k$$$ 步棋。在一次移动中,Taiga 选择一个非负整数 $$$\ell$$$ 并设置 $$$n \gets n + 2^{\ell}$$$。
Ryuuji 定义 分数 本实验的 一步作为将 $$$2^{\ell}$$$ 添加到基数 $$$2$$$ 中的当前数字时发生的二进制进位数。总计 分数 本实验的 是总和 分数 本实验的 超过所有 $$$k$$$ 移动。
大河想要总数 分数 本实验的 在 $$$k$$$ 移动后尽可能大。最大总数是多少 分数 本实验的 她能实现什么?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \lt 2^{30}$$$, $$$0 \le k \le 10^9$$$) — 初始整数和移动次数。
输出
对于每个测试用例,输出一个整数 - 最大总数 分数 本实验的 大河可以实现。
示例
输入复制
67 113 242 21048576 10023 2371 1
输出复制
34310053
注意
在第一个测试用例中,$$$(n,k)=(7,1)$$$ 和 $$$7=\mathtt{111}_2$$$。添加 $$$2^0$$$ 得到 $$$\mathtt{111}+\mathtt{1}=\mathtt{1000}$$$,它在位 $$$0,1,2$$$ 处产生进位。所以总分是$$$3$$$。
在第二个测试用例中,$$$(n,k)=(13,2)$$$ 和 $$$13=\mathtt{1101}_2$$$。首先我们添加$$$2^0$$$:$$$\mathtt{1101}+\mathtt{0001}=\mathtt{1110}$$$,这会创建一个进位。然后我们添加$$$2^1$$$:$$$\mathtt{1110}+\mathtt{0010}=\mathtt{10000}$$$,进位通过位$$$1,2,3$$$传播。总共有 $$$1+3=4$$$ 进位,因此得分为 $$${4}$$$。
在第三个测试用例中,$$$(n,k)=(42,2)$$$ 和 $$$42=\mathtt{101010}_2$$$。首先我们添加$$$2^1$$$:$$$\mathtt{101010}+\mathtt{000010}=\mathtt{101100}$$$,给出一个进位。接下来我们添加$$$2^2$$$:$$$\mathtt{101100}+\mathtt{000100}=\mathtt{110000}$$$,它在位$$$2$$$和$$$3$$$处生成进位。因此进位总数为$$$1+2=3$$$。
在第五个测试用例中,$$$(n,k)=(23,2)$$$ 和 $$$23=\mathtt{10111}_2$$$。首先我们添加$$$2^0$$$:$$$\mathtt{10111}+\mathtt{00001}=\mathtt{11000}$$$,它在位$$$0,1,2$$$处产生进位。然后我们添加$$$2^3$$$:$$$\mathtt{11000}+\mathtt{01000}=\mathtt{100000}$$$,在位$$$3$$$和$$$4$$$处产生进位。总共有 $$$3+2=5$$$ 进位,所以总分是 $$${5}$$$。