给你两个整数 $$$n$$$ 和 $$$k$$$。
你的任务是构造一个由 $$$k$$$ 非负整数 $$$a_1, a_2, \ldots, a_k$$$ 组成的序列 $$$a$$$ ,使得:
- $$$\sum_{i=1}^{k} a_i \le n$$$
- 设置位的总数,即 $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 尽可能大。
你只需要输出 $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 的最大可能值。
这里,$$$\operatorname{popcount}(x)$$$ 表示$$$x$$$ 的二进制表示中$$$1$$$ 的位数。例如,$$$\operatorname{popcount}(6) = \operatorname{popcount}((110)_2) = 2$$$,$$$\operatorname{popcount}(0) = 0$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
接下来的 $$$t$$$ 行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^6$$$) — 分别是序列的最大允许总和和序列的长度。
输出
对于每个测试用例,输出一个整数 - $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 的最大可能值。
示例
输入复制
62 13 16 214142 1372051000000 1001000000 1000000
输出复制
1241414213221000000
注意
在第一个测试用例中,$$$n=2$$$ 和 $$$k=1$$$。我们可以选择 $$$a = [1]$$$ 或 $$$a = [2]$$$。在这两种情况下,popcount 的总和都是 $$$1$$$。
在第二个测试用例中,$$$n=3$$$ 和 $$$k=1$$$。我们可以选择$$$a = [3]$$$,因为$$$(3)_2 = (11)_2$$$,$$$\operatorname{popcount}(3) = 2$$$。
在第三个测试用例中,$$$n=6$$$ 和 $$$k=2$$$。我们可以选择 $$$a = [3, 3]$$$。总和为 $$$3 + 3 = 6 \le 6$$$,总 popcount 为 $$$\operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4$$$。