Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Влад и нечётное упорядочение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Владислава есть $$$n$$$ карт с номерами $$$1, 2, \dots, n$$$. Он хочет выложить их в ряд следующим образом:

  • Сначала он выкладывает все карты с нечетными номерами от наименьшего к наибольшему.
  • Затем он выкладывает все карты, которые являются удвоенными нечетными числами, от наименьшего к наибольшему (т.е., $$$2$$$ умноженное на нечётное число).
  • Затем он выкладывает все карты, которые являются нечетными числами, умноженными на $$$3$$$, от наименьшего к наибольшему (т.е., $$$3$$$ умноженное на нечётное число).
  • Затем он выкладывает все карты, которые являются нечетными числами, умноженными на $$$4$$$, от наименьшего к наибольшему (т.е., $$$4$$$ умноженное на нечётное число).
  • И так далее, пока все карты не будут выложены.
Какая карта будет $$$k$$$-й, которую он выложит в этом процессе? После того, как Влад положил карту, он не может использовать ее снова.
Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$) — количество карт у Влада и позицию карты, которую нужно вывести.

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

Для каждого набора входных данных выведите одно целое число — $$$k$$$-ю карту, которую выложит Влад.

Пример
Входные данные
11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000
Выходные данные
1
3
5
7
2
6
4
1
27
37
536870912
Примечание

В первых семи наборах входных данных примера $$$n=7$$$. Влад выкладывает карты следующим образом:

  • Сначала — все карты с нечетными номерами в порядке $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.
  • Затем — все карты, которые являются удвоенными нечетными числами, в порядке $$$2$$$, $$$6$$$.
  • Затем нет оставшихся карт, которые являются нечетными числами, умноженными на $$$3$$$. (У Влада есть только по одной карте каждого числа.)
  • Затем — все карты, которые являются нечетными числами, умноженными на $$$4$$$, и есть только одна такая карта: $$$4$$$.
  • Больше карт не осталось, поэтому Влад останавливается.
Таким образом, порядок карт будет $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$2$$$, $$$6$$$, $$$4$$$.