D. Цепи переносов Тайги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Чудеса не происходят с теми, кто просто ждет.
— Торадора!

После занятий в старшей школе Охаси Рюдзи даёт Тайге целое положительное число $$$n$$$ и ставит простую задачу.

Они будут играть ровно $$$k$$$ ходов. На одном ходу Тайга выбирает целое неотрицательное число $$$\ell$$$ и присваивает $$$n \gets n + 2^{\ell}$$$.

Рюдзи определяет счёт одного хода как количество двоичных переносов, которые происходят при сложении $$$2^{\ell}$$$ с текущим числом в системе счисления с основанием $$$2$$$. Общий счёт — это сумма счётов за все $$$k$$$ ходов.

Тайга хочет, чтобы общий счёт был как можно больше после $$$k$$$ ходов. Какой максимальный общий счёт она может достичь?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \lt 2^{30}$$$, $$$0 \le k \le 10^9$$$) — начальное целое число и количество ходов.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный общий счёт, который Тайга может достичь.

Пример
Входные данные
6
7 1
13 2
42 2
1048576 100
23 2
371 1
Выходные данные
3
4
3
100
5
3
Примечание

В первом наборе входных данных, $$$(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}$$$.