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