Коды Грея

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность

0
1
-

Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди $0$, а ко второй отображенной половине $1$. Получим последовательность:

00
01
11
10

Продолжая процесс, на следующем шаге получим последовательность из $8$ чисел. Справа от кода находится его десятичное значение.

000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

Приведенные последовательности называются кодами Грея длины $n=1,2,3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $t(t\le 250000)$. Каждая следующая строка содержит два числа: $n(1\le n\le 30)$ и $k(0\le k<2^n)$.

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

Для каждого теста в отдельной строке выведите число, которое находится в $k$ - ой позиции последовательности кодов Грея длины $n$.

Примеры