B. Бинарная кофейня
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Тёма оказался в бинарной кофейне. Это очень популярное и необычное место.

Кофейня предлагает посетителям $$$k$$$ разных вкусных десертов. Десерты нумеруются от $$$0$$$ до $$$k-1$$$. Стоимость $$$i$$$-о десерта составляет $$$2^i$$$ монет, ведь это бинарная кофейня! Тёма готов потратить не более $$$n$$$ монет на дегустацию десертов. При этом ему неинтересно покупать любой десерт более одного раза, ведь для оценки вкуса достаточно и одного.

Сколькими различными способами он может купить несколько десертов (возможно ноль) для дегустации?

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

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

Далее следует $$$t$$$ строк, каждая из которых описывает один набор входных данных.

В единственной строке каждого набора задано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 10^9$$$) — количество монет, которые Тёма готов потратить, и количество десертов в бинарной кофейне.

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

Выведите $$$t$$$ целых чисел, $$$i$$$-е из которых должно быть равно ответу на $$$i$$$-й набор входных данных — количеству способов купить десерты для дегустации.

Пример
Входные данные
5
1 2
2 1
2 2
10 2
179 100
Выходные данные
2
2
3
4
180
Примечание

Варианты для первого набора входных данных: {}, {1}

Варианты для второго набора входных данных: {}, {1}

Варианты для третьего набора входных данных: {}, {1}, {2}

Варианты для четвёртого набора входных данных: {}, {1}, {2}, {1, 2}