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?

Input

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.

Output

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

Note

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}$.