Коды Грея
Коды Грея
Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
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. Каждые два соседних кода отличаются одним битом.
Giriş verilənləri
Первая строка содержит количество тестов t~(t \le 250000). Каждая следующая строка содержит два числа: n~(1 \le n \le 30) и k~(0 \le k < 2^n).
Çıxış verilənləri
Для каждого теста в отдельной строке выведите число, которое находится в k - ой позиции последовательности кодов Грея длины n.
Nümunə
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
0 1 0 1 3 2 0 1 3 2 6 7 5 4