Двійкова проти негативної двійкової

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

Вхідні дані

Перший рядок вхідного файлу містить число тестів. Кожен тест представляє одне ціле число N (1 < N ≤ 10^9) в окремому рядку.

Вихідні дані

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

Приклади