Stable Relative Sorting of 0, 1, and 2

Given an array containing only the elements 0, 1, and 2, reorder the array so that all the 0s appear first, followed by all the 1s, and finally all the 2s. The relative order of the elements within each group (0s, 1s, and 2s) must be preserved.

For example, if the input array is [2, 0, 2, 1, 1], the output should be [0, 1, 1, 2, 2].

inputFormat

The input is read from standard input. The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N, the number of elements in the array. The second line contains N space-separated integers, each being either 0, 1, or 2.

outputFormat

For each test case, output a single line containing the reordered array, with the elements separated by a single space. The output is written to standard output.## sample

1
5
2 0 2 1 1

0 1 1 2 2