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? 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 < 2^{30}), (0 \le k \le 10^9)) — the initial integer and the number of moves. 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))