Sharkovski's Ordering#6244
Sign in

Sharkovski's Ordering

1 second
128 megabytes
Very easy

In a 1964 paper on continuous mappings of the reals into the reals, Alexandr Sharkovski introduced the following ordering of the positive integers:

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

This is how Ciesielski and Pogoda (2008) describe this ordering:

"First come the odd numbers, beginning with 3, arranged in increasing order. This sequence is repeated with each odd integer multiplied by 2. The initial sequence is again repeated with each odd integer multiplied by 2^2, and so on. The terminal sequence consists of nonnegative powers of 2 arranged in decreasing order (note that 1 = 2^0)."

Given several sequences of unsigned integers, write a program that outputs the numbers of each sequence in Sharkovski's order.

Input

The first line contains an integer (0 \le n \le 255) — the number of test cases.

Each of the next lines contains a non-empty sequence of up to unsigned integers (not necessarily distinct), each not exceeding , separated by whitespace and terminated by .

Output

For each test case, output the integers (excluding the terminating ) arranged in Sharkovski's order, separated by a single space.

Examples

Example 1

Loading
Loading