Sort an array A where each of the elements belong to the set: {0, 1, 2}.

Expected Time Complexity: O(n)

Try to solve it without storing the count of 0s, 1s and 2s.

Example:

A: [2, 2, 0, 1]
Result: [0, 1, 2, 2]

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case the input has two lines:

• An integer 'n' denoting the size of the array A.
• n space separated integers denoting the elements of array A.

Output Format

For each test case, the output has a line containing n space separated integers denoting the elements of the sorted array A.

Sample Input

2
5
1 0 1 2 2
4
1 0 0 0

Expected Output

0 1 1 2 2
0 0 0 1

Constraints

1 <= T <= 10
1 <= n <= 105
0 <= Ai <= 2