Занятие 18

Уроборос — архаический образ, часто встречающийся в алхимических трактатах и представляющий собой змею, заглатывающую свой хвост.

Числа Уробороса – это двоичные числа из `2^n` бит, которые образованы из двоичных чисел 0 до `2^n-1` следующим образом. Для этого нужно разместить `2^n` бит по кругу, так чтобы получилось `2^n` различных подстрок из `n` бит при движении кругу.

Например, для `n=2` существует четыре числа Уробороса  – 0011, 0110, 1100 и 1001. В таблице и на рисунке показано, как можно найти все подстроки в числе 0011:

Ваше программа должна вычислять `o(n,k)`, где `n\ >\ 0` и `0\ ≤\ k\ <\ 2^n`. Эта функция вычисляет `k`-е число в наименьшем числе Уробороса порядка `n`.

В первой строке ввода содержится одно целое число `T\ (0\ <\ T\ <\ 300)` – число тестов. Далее следует `T` строк, в каждой строке содержится два целых числа `n\ (0<n<22)` и `k\ (0\ ≤\ k\ <\ 2^n`).

Для каждого теста вы должны вычислить функцию `o(n,k)` и напечатать результат на отдельной строке.

4 
2 0
2 1
2 2
2 3

0
1
3
2