CF2173D.Taiga's Carry Chains

Miracles don't happen to those who just wait.

— Toradora!

After classes at Ohashi High School, Ryuuji hands Taiga a positive integer $n$ and sets a simple challenge.

They will play for exactly $k$ moves. In a single move, Taiga chooses a non-negative integer $\ell$ and sets $n \gets n + 2^{\ell}$.

Ryuuji defines the score of one move as the number of binary carries that occur when adding $2^{\ell}$ to the current number in base $2$. The total score is the sum of score over all $k$ moves.

Taiga wants the total score to be as large as possible after $k$ moves. What is the maximum total score she can achieve?

奇迹不会眷顾那些只会等待的人。

——《龙与虎》！

在大桥高中的课程结束后，龙儿交给大河一个正整数 $n$，并设下了一个简单的挑战。

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

龙儿将单轮操作的“得分”定义为：在二进制下将 $2^{\ell}$ 加到当前数字时所发生的进位次数。总得分为 $k$ 轮操作得分之和。

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The only line of each test case contains two integers $n$ and $k$ ($1 \le n \lt 2^{30}$, $0 \le k \le 10^9$) — the initial integer and the number of moves.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$1 \le n \lt 2^{30}$，$0 \le k \le 10^9$）——分别表示初始整数和操作次数。

For each test case, output a single integer — the maximum total score that Taiga can achieve.

对于每个测试用例，输出一个整数——即太郎所能获得的最高总分。

In the first test case, $(n,k)=(7,1)$ and $7=\mathtt{111}_2$. Adding $2^0$ gives $\mathtt{111}+\mathtt{1}=\mathtt{1000}$, which produces carries at bits $0,1,2$. So the total score is $3$.

In the second test case, $(n,k)=(13,2)$ with $13=\mathtt{1101}_2$. First we add $2^0$: $\mathtt{1101}+\mathtt{0001}=\mathtt{1110}$, which creates one carry. Then we add $2^1$: $\mathtt{1110}+\mathtt{0010}=\mathtt{10000}$, with carries propagating through bits $1,2,3$. In total there are $1+3=4$ carries, so the score is ${4}$.

In the third test case, $(n,k)=(42,2)$ and $42=\mathtt{101010}_2$. First we add $2^1$: $\mathtt{101010}+\mathtt{000010}=\mathtt{101100}$, giving one carry. Next we add $2^2$: $\mathtt{101100}+\mathtt{000100}=\mathtt{110000}$, which generates carries at bits $2$ and $3$. Thus the total number of carries is $1+2=3$.

In the fifth test case, $(n,k)=(23,2)$ and $23=\mathtt{10111}_2$. First we add $2^0$: $\mathtt{10111}+\mathtt{00001}=\mathtt{11000}$, which produces carries at bits $0,1,2$. Then we add $2^3$: $\mathtt{11000}+\mathtt{01000}=\mathtt{100000}$, producing carries at bits $3$ and $4$. Altogether there are $3+2=5$ carries, so the total score is ${5}$.

在第一个测试用例中，$(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}$。