Problem: You are given an integer n and an array a_1, a_2, …, a_n. You should reorder the elements of the array a in such way that the sum of MEX on prefixes (i-th prefix is a_1, a_2, …, a_i) is maximized.

Formally, you should find an array b_1, b_2, …, b_n, such that the sets of elements of arrays a and b are equal (it is equivalent to array b can be found as an array a with some reordering of its elements) and ∑_{i=1}^{n} MEX(b_1, b_2, …, b_i) is maximized.

MEX of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set.

For example, MEX(\{1, 2, 3\}) = 0, MEX(\{0, 1, 2, 4, 5\}) = 3.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100).

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 100).

Output

For each test case print an array b_1, b_2, …, b_n — the optimal reordering of a_1, a_2, …, a_n, so the sum of MEX on its prefixes is maximized.

If there exist multiple optimal answers you can find any.

Example

Input


3
7
4 2 0 1 3 3 7
5
2 2 8 6 9
1
0


Output


0 1 2 3 4 7 3 
2 6 8 9 2 
0 

Note

In the first test case in the answer MEX for prefixes will be: 

  1. MEX(\{0\}) = 1 
  2. MEX(\{0, 1\}) = 2 
  3. MEX(\{0, 1, 2\}) = 3 
  4. MEX(\{0, 1, 2, 3\}) = 4 
  5. MEX(\{0, 1, 2, 3, 4\}) = 5 
  6. MEX(\{0, 1, 2, 3, 4, 7\}) = 5 
  7. MEX(\{0, 1, 2, 3, 4, 7, 3\}) = 5 

The sum of MEX = 1 + 2 + 3 + 4 + 5 + 5 + 5 = 25. It can be proven, that it is a maximum possible sum of MEX on prefixes.

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
      int testCases = scanner.nextInt();
      int length;
      while(testCases-- >0){
          length = scanner.nextInt();
          Set <Integer> array = new TreeSet<Integer>();
          List<Integer> duplicate = new ArrayList<Integer>();
          for(int i=0;i<length;i++){
              int el = scanner.nextInt();
              if(!array.contains(el))
                array.add(el);
              else
                  duplicate.add(el);

          }
          List<Integer> arr = new ArrayList<Integer>(array);
          arr.addAll(duplicate);
          for(int i=0;i<arr.size();i++){
              System.out.print(arr.get(i) + " ");
          }
//
//          for(int i=0;i<array.size();i++){
//              System.out.println(array.equals(mex));
//              if(array.){
//                  mex++;
//              }
//              sum+=mex;
//          }
      }
    }
}

//////import java.util.Arrays;
//////
////////public class Main{
//////public class Main {
//////
//////    private static double getMaxValue(int wt[], int val[], int capacity){
//////        ItemValue iVal [] = new ItemValue[wt.length];
//////
//////        for(int i=0;i<wt.length;i++){
//////            iVal[i] = new ItemValue(wt[i],val[i],i);
//////        }
//////
//////        Arrays.sort(iVal,(o1, o2) -> Double.compare(o2.cost, o1.cost));
//////
//////        double totalValue = 0;
//////        for(ItemValue i : iVal){
//////            int curWt = (int)i.wt;
//////            int curVal = (int)i.val;
//////
//////            if(capacity - curWt > 0){{
//////                capacity -= curWt;
//////                totalValue += curVal;
//////            }else{
//////                double fraction = ((double) capacity / (double) curWt);
//////                totalValue += fraction * curVal;
//////                capacity = (int) (capacity - (curWt * fraction));
//////                break;
//////            }
//////        }
//////        return totalValue;
//////    }
//////
//////    static class ItemValue {
//////        double cost;
//////        double wt,val,ind;
//////
//////        public ItemValue(double wt, double val, int ind) {
//////            this.cost =  val / wt;
//////            this.wt = wt;
//////            this.val = val;
//////            this.ind = ind;
//////        }
//////    }
//////
//////    public static void main(String[] args) {
//////        int wt[] = {10,40,20,30};
//////        int val[] = {60,40,100,120};
//////        int capacity = 50;
//////
//////        double maxValue = getMaxValue(wt,val,capacity);
//////
//////        System.out.println("Max value is " + maxValue);
//////    }
//////}
////
//////import java.util.Arrays;
//////
//////public class Main{
//////
//////    public static int calcMaxProfits(char jobIds[], int deadlines[], int profits[]){
//////         Job jobArr[] = new Job[jobIds.length];
//////
//////         for(int i=0;i<jobIds.length;i++){
//////             jobArr[i] = new Job(jobIds[i],deadlines[i],profits[i]);
//////         }
//////        Arrays.sort(jobArr,(obj1,obj2)->obj2.profits - obj1.profits);
//////        int arrPos[] = new int[jobIds.length];
//////        int j = 0;
//////        for(int i=0;i<jobIds.length;i++){
//////            j = jobArr[i].deadline - 1;
//////            while(j>=0){
//////                if(arrPos[j] == 0){
//////                    arrPos[j] = jobArr[i].profits;
//////                    break;
//////                }else{
//////                    j--;
//////                }
//////            }
//////        }
//////        int maxProfits = 0;
//////        for(int prof: arrPos){
//////            maxProfits += prof;
//////        }
//////         return maxProfits;
//////    }
//////
//////    static class Job{
//////        char jobId;
//////        int deadline;
//////        int profits;
//////
//////        public Job(char jobId, int deadline, int profits) {
//////            this.jobId = jobId;
//////            this.deadline = deadline;
//////            this.profits = profits;
//////        }
//////    }
//////
//////    public static void main(String[] args) {
//////        char jobIds [] = {'a','b','c','d'};
//////        int deadlines[] = {4,1,1,1};
//////        int profits [] = {20,10,40,30};
//////
//////        int maxProfits = calcMaxProfits(jobIds,deadlines,profits);
//////        System.out.println("Max profits are " + maxProfits);
//////    }
//////}
//
//import java.util.HashMap;
//import java.util.Scanner;
//
//public class Main{
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int noOfStudents = scanner.nextInt();
//        int students[] = new int[noOfStudents];
//
//        HashMap<Number,Number> h = createArr(students,noOfStudents,scanner);
//
//        int i =0;
//        String str = "";
//        int student = 1;
//        while((int) h.get(1) != 0 &&(int) h.get(2) !=0 && (int) h.get(3) != 0){
//            if(students[i] == student){
//                if(student == 3){
//                    student = 0 ;
//                }else{
//                    student++;
//                }
//                str += i;
//                h.put(student,(int) h.get(student)-1);
//                students[i] = 0;
//            }else{
//                i++;
//            }
//            if(i == students.length){
//                i = 0;
//            }
//        }
//    }
//
//    public static HashMap<Number, Number> createArr(int arr[], int length, Scanner scanner){
//        HashMap<Number,Number> h = new HashMap<Number,Number>();
//        int one = 0;
//        int two = 0;
//        int three = 0;
//        for(int i=0;i<length;i++){
//            int el = scanner.nextInt();
//            arr[i] = el;
//            if(el == 1){
//                one++;
//            }else if (el == 2){
//                two++;
//            }else{
//                three++;
//            }
//        }
//        h.put(1,one);
//        h.put(2,two);
//        h.put(3,three);
//        return h;
//    }
//}
//
////import java.util.Scanner;
////
////public class Main {
////    public static void main(String[] args) {
////
////    }
////
////    private static int create2dArr(Scanner scanner, int twdDArr[][],int rows,int cols, int k){
////        int count = 0;
////        int el;
////        for(int i=0;i<rows;i++){
////            for(int j=0;j<cols;j++){
////               el = scanner.nextInt();
////               if(el >= k)count++;
////               twdDArr[i][j] = el;
////            }
////        }
////        return count;
////    }
////
////    private static int squareMatrixAvg(int twoDArr[][],int rows,int cols,int max){
////        int k = 2;
////        int count = 0;
////        while(rows-k+1 != 1){
////
////            for(int i=0;i< rows-k+1;i++){
////                for(int j=0;j< cols - k + 1; j++){
////                    int sum =0;
////                    int length = 0;
////                    for(int p=i;p<k+i;p++){
////                        for(int q=j;q<k+j;q++){
////                            sum+=twoDArr[p][q];
////                            length++;
////                        }
////                    }
////                    if((double)sum/ length >= (double)max)count++;
////                }
////            }
////            k++;
////        }
////        return count;
////    }
////}