eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Коды Грея

Коды Грея

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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.

Пример

Входные данные #1
14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
Выходные данные #1
0
1
0
1
3
2
0
1
3
2
6
7
5
4