There is a country which recently got invaded by a fleet of aliens. They started living with the people there. Relations between the aliens and humans were generally bitter. The government at the center decided that they will divide the country into 2 states (initially there were none). There are N citizens in the country; the aliens are denoted by -1, while the humans are denoted by 1. You are a Government official, who has been assigned the task to send the aliens to one state and the humans to the other. The citizens queue up at a place. The queue is denoted by an array, where each element is either 1 or -1 denoting humans and aliens, respectively.
Bring the aliens to the left side of the queue and the humans to the right.

Input
The first line of input contains T, the number of test cases. The first line of each test case contains N, the number citizens, the next line consist of the elements of the array A.

Output
For each test case output the sequence that is formed after arranging the aliens to the left side of the queue and the humans to the right.

Constraints
Should contain all the constraints on the input data that you may have. Format it like:

1 ≤ T ≤ 100
1 ≤ N ≤ 100

Example
Input:
3
2
1 -1
4
-1 1 -1 -1
5
1 1 1 -1 -1

Output:
-1 1
-1 -1 -1 1
-1 -1 1 1 1

见题面

见题面