D. Taiga's Carry Chains

题目描述

奇迹不会降临到只会等待的人身上。 ——《龙与虎》

放学后，龙儿交给逢坂大河一个非负整数 $n$ ，并发起了一个简单的挑战。

他们将恰好进行 $k$ 轮操作。在每一轮操作中，大河选择一个非负整数 $\ell$ ，并将 $n$ 更新为 $n + 2^\ell$ 。

龙儿定义一轮操作的得分为：将 $2^\ell$ 加到当前数时，在二进制表示下产生的进位次数。总得分是所有 $k$ 轮操作得分的总和。

大河希望在 $k$ 轮操作后总得分尽可能大。她能达到的最大总得分是多少？

第一行包含一个整数 $t$ （ $1 \le t \le 1000$ ），表示测试用例的数量。

每个测试用例包含一行两个整数 $n$ 和 $k$ （ $1 \le n < 2^{30}$ ， $0 \le k \le 10^9$ ）—— 初始整数和操作轮数。

对于每个测试用例，输出一个整数，表示最大可能的总得分。

6
7 1
13 2
42 2
1048576 100
23 2
371 1

第一个测试用例： $n=7$ （二进制 $\mathtt{111}$ ）。选择 $\ell=0$ ，添加 $2^0=1$ ，得到 $\mathtt{1000}$ 。二进制加法中产生了 3 次进位（位 0、1、2），总得分 3。
第二个测试用例： $n=13$ （二进制 $\mathtt{1101}$ ）。第一轮添加 $2^0=1$ ，得到 $\mathtt{1110}$ ，产生 1 次进位；第二轮添加 $2^1=2$ ，得到 $\mathtt{10000}$ ，产生 3 次进位（位 1、2、3）。总得分 $1+3=4$ 。
第三个测试用例： $n=42$ （二进制 $\mathtt{101010}$ ）。第一轮添加 $2^1=2$ ，得到 $\mathtt{101100}$ ，产生 1 次进位；第二轮添加 $2^2=4$ ，得到 $\mathtt{110000}$ ，产生 2 次进位（位 2、3）。总得分 $1+2=3$ 。
第五个测试用例： $n=23$ （二进制 $\mathtt{10111}$ ）。第一轮添加 $2^0=1$ ，得到 $\mathtt{11000}$ ，产生 3 次进位（位 0、1、2）；第二轮添加 $2^3=8$ ，得到 $\mathtt{100000}$ ，产生 2 次进位（位 3、4）。总得分 $3+2=5$ 。