Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди , а ко второй отображенной половине . Получим последовательность:
Продолжая процесс, на следующем шаге получим последовательность из чисел. Справа от кода находится его десятичное значение.
Приведенные последовательности называются кодами Грея длины . Всего существует разных кодов длины . Каждые два соседних кода отличаются одним битом.
Первая строка содержит количество тестов . Каждая следующая строка содержит два числа: и .
Для каждого теста в отдельной строке выведите число, которое находится в - ой позиции последовательности кодов Грея длины .