CF2173D Taiga's Carry Chains

奇迹不会降临到只是等待的人头上。 ——《龙与虎！》 在大桥高中的放学后，龙儿给了大河一个正整数 $n$，并设定了一个简单的挑战。 他们正好进行 $k$ 步操作。在每一步操作中，大河选择一个非负整数 $\ell$，然后将 $n$ 置为 $n \gets 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$），表示初始整数和操作步数。

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

在第一个测试用例中，$(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$。 由 ChatGPT 5 翻译