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

Боб устал проигрывать Алисе и, чтобы точно больше не проиграть, решил выбрать игру так, чтобы гарантированно победить. Боб загадал число от $$$1$$$ до $$$n$$$, причем известно, что $$$n = 2^d$$$ для некоторого целого неотрицательного числа $$$d$$$. Изначально Алисе известно, чётное загаданное число или нет.

За одно действие Алиса может либо уменьшить его вдвое, либо вычесть $$$1$$$. Уменьшить число вдвое Алиса может только в том случае, если текущее число чётное. Ходит только Алиса.

После своего действия Алиса получает от Боба ответ: либо $$$-1$$$, что означает, что число стало равно $$$0$$$, и Алиса выиграла, либо неотрицательное целое число $$$x$$$. Если обозначить текущее число за $$$a$$$, то для $$$x$$$ одновременно выполнены условия:

  1. $$$a$$$ делится нацело на $$$2^x$$$.
  2. $$$a$$$ не делится нацело на $$$2^{x+1}$$$.

Например, если $$$a=5$$$, то $$$x=0$$$, так как $$$5$$$ делится на $$$2^0=1$$$ и не делится на $$$2^1=2$$$, а если $$$a=12$$$, то $$$x=2$$$, так как $$$12$$$ делится на $$$2^2=4$$$ и не делится на $$$2^3=8$$$.

Можно показать, что для любого целого $$$a \gt 0$$$ существует единственное такое $$$x$$$.

Боб всё-таки боится, что Алиса выиграет, поэтому в игре будет не более $$$k$$$ ходов. Также Боб хочет отыграться по максимуму, поэтому он хочет сыграть как можно больше игр. По заданным $$$n$$$ и $$$k$$$ посчитайте количество изначальных чисел от $$$1$$$ до $$$n$$$ таких, что Алиса, играя оптимально, не сможет выиграть не более чем за $$$k$$$ ходов.

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

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

В единственной строке каждого набора входных данных содержатся $$$2$$$ целых числа $$$n$$$ и $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — ограничение на загаданное число и максимальное количество ходов Алисы соответственно. Гарантируется, что $$$n = 2^d$$$ для некоторого целого неотрицательного числа $$$d$$$.

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

Для каждого набора входных данных выведите количество чисел от $$$1$$$ до $$$n$$$ таких, что Алиса, играя оптимально, не сможет победить не более чем за $$$k$$$ ходов.

Пример
Входные данные
7
4 1
4 2
4 3
4 4
4 5
16 5
16 1
Выходные данные
3
2
0
0
0
4
15
Примечание

В первом примере подходят $$$a=2$$$, $$$a=3$$$ и $$$a=4$$$, так как из $$$a=1$$$ можно попасть в $$$0$$$ за $$$1$$$ операцию, а для остальных значений можно показать, что потребуется хотя бы $$$2$$$ операции.

Во втором примере подходят $$$a=3$$$ и $$$a=4$$$, так как при $$$a=2$$$ Алиса может выиграть за $$$2$$$ операции.

В третьем, четвертом и пятом примерах нет подходящих $$$a$$$, так как для $$$a=3$$$ и $$$a=4$$$ Алиса может выиграть за $$$3$$$ операции.