D. Taiga's Carry Chains
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.

Example
Input
6
7 1
13 2
42 2
1048576 100
23 2
371 1
Output
3
4
3
100
5
3
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}$$$.