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

Двоичная против отрицательной двоичной

Двоичная против отрицательной двоичной

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

Отрицательная двоичная система - это позиционная система счисления с основанием равным -2. Точно так же, как и в двоичной системе, в этой системе можно выразить любое неотрицательное целое число. Например, 3_10 = 111_{-2}. Впрочем отрицательная двоичная система может задавать отрицательные числа, точно так же легко, как и положительные: -3_10 = 1101_{-2}. Некоторые числа выражаются одинаково в обеих системах. В этой задаче мы хотим узнать n-те целое число, которое имеет такое же представление в двоичной и отрицательной двоичной системах.

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

Первая строка входного файла содержит количество тестов. Каждый тест задаёт одно целое число N (1 < N10^9) в отдельной строке.

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

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

Пример

Входные данные #1
3
1
10
100
Выходные данные #1
0
65
5125
Источник Всеукраинская студенческая олимпиада по программированию, ФИНАЛ, Харьков 15 октября 2011, 2-я лига