Monk and Tasks

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 with tasks for N days in the form of an array A, where the elements of the array represent the number of tasks each day.

The number of tasks performed by Monk A on the ith day is the number of 1s in the binary representation of A_i.

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

Input Specification

The first line of the input contains an integer T, where T is the number of test cases (1 ≤ T ≤ 100). The first line of each test case contains N, where N is the number of days (1 ≤ N ≤ 10⁵). The second line of each test case contains array A, having N elements, where A_i represents the number of tasks provided by Monk D to Monk A on the ith day (1 ≤ A_i ≤ 10¹⁸).

Output Specification

Print all the tasks provided to Monk A in nondecreasing order of the number of tasks performed by him.

Note

If more than one number has the same number of 1s (set bits), print them in the same order as they appeared in the input.

Sample Input

1. 1
2. 4
3. 3 4 7 10

download as text file

Output for Sample Input

1. 4 3 10 7

download as text file

Sample Explanation

In the sample input, T = 1 and N = 4, where N is the number of days. Tasks provided to Monk A on the first day is 3, and the binary representation of 3 is {11}₂, which contains two 1s. Tasks provided to Monk A on the second day is 4, and the binary representation of 4 is {100}₂, which contains one 1. Tasks provided to Monk A on the third day is 7, and the binary representation of 7 is {111}₂, which contains three 1s. Tasks provided to Monk A on the fourth day is 10, and the binary representation of 10 is {1010}₂, which contains two 1s. So the output is: 4 3 10 7.