Siddhartha Sahu is Evil and he strikes when no one is looking. Apparently he loves odd numbers very much which i find very odd. I was trying to set a simple question based on Arithmetic Progression. I wrote some arithmetic progressions on a white board.The progressions consisted of at least 4 terms which where all positive integers. In my absence Sahu came to room and decided to make all the numbers on the board odd.
He did this by repeatedly finding an even number X and replacing it X/2. He continued this till no even numbers remained.

Now Interestingly your task is to restore the original progression I wrote on the board. If there are multiple such sequences , print the lexicographically smallest one. A solution will always exist.

Input

First line begins with T denoting number of test cases.
Each Test case begins with N denoting the length of the sequence.
Next Line contains N space separated Integers which are part of sequence corrupted by Evil Sahu.

Output

For every Test case , print N integers on one line (space separated ) which denotes the original Sequence written on the board.
There wont be any space after the last Integer of the output series

Constraints

T<=100
4<=N<=50
All Integers of corrupted sequence will be less than 1000.
All Intgeres of the original sequence will fit into a 32 bit Integer.

Sample Input
``` 3 5 1 1 3 1 5 5 9 7 5 3 1 4 1 1 1 1 ```

Sample Output
``` 1 2 3 4 5 9 7 5 3 1 1 1 1 1 ```

Problem Setter : Arjun Singh Bhatia

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0