e-olymp
Задачи

Коды Грея

Коды Грея

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

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. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов n (не более 250000). Каждая следующая строка содержит два числа: n (1n30) и k (0k < 2n).

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #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