Monk A loves to complete all his tasks just before the deadlines for introducing unwanted thrill in his life. But, there is another Monk D who hates this habit of Monk A and thinks it's risky.

To test Monk A, Monk D provided him tasks for N days in the form of an array Array, where the elements of the array represent the number of tasks.

The number of tasks performed by Monk A on the i^th day is the number of ones in the binary representation of Array_i.

Monk A is fed up of Monk D, so to irritate him even more, he decides to print the tasks provided in non-decreasing order of the tasks performed by him on each day. Help him out!

Input:
The first line of input contains an integer T, where T is the number of test cases.
The first line of each test case contains N, where N is the number of days.
The second line of each test case contains Array array having N elements, where Array_i represents the number of tasks provided by Monk D to Monk A on i^th day.

Output:
Print all the tasks provided to Monk A in the non-decreasing order of number of tasks performed by him.

Constraints:
1 <= T <= 100
1 <= N <= 10⁵
1 <= Array_i <= 10¹⁸

Note:
If two numbers have the same number of ones (set bits), print the one which came first in the input first, and then the other one, as in the input.