Негативна двійкова система - це позиційна система числення з основою рівною \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}-те ціле число, яке має таке ж представлення в двійковій і негативній двійковій системах в окремому рядку.