Порядок Шарковського#6244

Порядок Шарковського

1 секунда

128 мегабайтів

Дуже легка

У статті 1964 року про неперервні відображення дійсних чисел, Олександр Шарковський увів таке впорядкування додатних цілих чисел:

3 ◃ 5 ◃ 7 ◃ 9 ◃ \dots ◃ 3 \times 2 ◃ 5 \times 2 ◃ 7 \times 2 ◃ \dots ◃ 3 \times 2^{2} ◃ 5 \times 2^{2} ◃ \dots ◃ 2^{3} ◃ 2^{2} ◃ 2 ◃ 1

3 \triangleleft 5 \triangleleft 7 \triangleleft 9 \triangleleft \ldots \triangleleft 3 \times 2 \triangleleft 5 \times 2 \triangleleft 7 \times 2 \triangleleft \ldots \triangleleft 3 \times 2^2 \triangleleft 5 \times 2^2 \triangleleft \ldots \triangleleft 2^3 \triangleleft 2^2 \triangleleft 2 \triangleleft 1

Цисільський та Погода (2008) описують це впорядкування так:

"Спочатку йдуть непарні числа, починаючи з 3, впорядковані за зростанням. Далі ця послідовність повторюється, кожне непарне число множиться на 2. Знову повторюється початкова послідовність, тільки кожне непарне число множиться на $2^{2}$ 2^2, і так далі. Кінцева послідовність складається з невід’ємних ступенів 2, впорядкованих за спаданням (зауважимо, що 1 = $2^{0}$ 2^0)."

Дано кілька послідовностей беззнакових цілих чисел. Напишіть програму, яка для кожної послідовності виведе числа у порядку Шарковського.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $0 \leq n \leq 255$ 0 \le n \le 255) — кількість тестових випадків.

Кожен з наступних $n$ рядків містить непорожню послідовність до $255$ беззнакових цілих чисел (не обов'язково різних), не більших за $65535$ , відокремлених пропуском та завершених $0$ .

Вихідні дані

Для кожного тесту виведіть числа (окрім завершального $0$ ), впорядковані за порядком Шарковського, через один пропуск.

Приклади

Приклад 1