Двоичная против отрицательной двоичной
Отрицательная двоичная система - это позиционная система счисления с основанием равным -2. Точно так же, как и в двоичной системе, в этой системе можно выразить любое неотрицательное целое число. Например, 3_10 = 111_{-2}. Впрочем отрицательная двоичная система может задавать отрицательные числа, точно так же легко, как и положительные: -3_10 = 1101_{-2}. Некоторые числа выражаются одинаково в обеих системах. В этой задаче мы хотим узнать n-те целое число, которое имеет такое же представление в двоичной и отрицательной двоичной системах.
Входные данные
Первая строка входного файла содержит количество тестов. Каждый тест задаёт одно целое число N (1 < N ≤ 10^9) в отдельной строке.
Выходные данные
Для каждого теста n-тое целое число, которое имеет такое ж представление в двоичной и отрицательной двичной системах в отдельной строке.