Problem: Sayaka Saeki is a member of the student council, which has n other members (excluding Sayaka). The i-th member has a height of a_i millimeters.

It's the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members u and v on a line is considered photogenic if their average height is an integer, i.e. (a_u + a_v)/(2) is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.

Input

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

The first line of each test case contains a single integer n (2 ≤ n ≤ 2000) — the number of other council members.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the heights of each of the other members in millimeters.

It is guaranteed that the sum of n over all test cases does not exceed 2000.

Output

For each test case, output on one line n integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.

Example

Input


4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9


Output


1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18 

Note

In the first test case, there is one photogenic pair: (1, 1) is photogenic, as (1+1)/(2)=1 is integer, while (1, 2) isn't, as (1+2)/(2)=1.5 isn't integer.

In the second test case, both pairs are photogenic.

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main {
	//  Solution 
	    public static void main(String args[])
	    {
	    	int t=in.nextInt();
	    	while(t-->0) {
	    		ArrayList<Integer>lop=new ArrayList();
	    		int n=in.nextInt();
	    		while(n-->0) {
	    			int x=in.nextInt();
	    			if(x%2==0) {
	    				out.append(x+" ");
	    			}else {
	    				lop.add(x);
	    			}
	    		}
	    		for(int x:lop)
	    			out.append(x+" ");
	    		out.append("\n");
	    	}
	    	out.close();
    }
	 
    static long mod=1000000007L;
    static long gcd(long a,long b) {
    	if(a==0)
    		return b;
    	return gcd(b%a,a);
    }
    static long dp[][][];
   
    static Reader in=new Reader();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}
class node implements Comparable<node> {
int val,pos;
node(int val,int pos){
	this.pos=pos;this.val=val;
}
@Override
public int compareTo(node o) {
	
	return val-o.val;
}
 
 
}
class xtree{
	public xtree(int n,int a[]) {
		this.a=a;
		seg=new int[n*4];
		//lazy=new int[n*4];
		build(1,0,n-1);
	}
	int seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        //check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = seg[2*p]+ seg[2*p+1];
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	       // check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        //check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
    
 
    
    int get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return 0; 
        
        return get(2*p,s,(s+e)/2,a,b)+ get(2*p+1,(s+e)/2+1,e,a,b);
    }
}
 
class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}
 class LongestCommonSubsequence 
{ 
  
  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	 int lcs( char[] X, char[] Y, int m, int n ,int K) 
	  { 
		 int L[][] = new int[m+1][n+1]; 
		 int ans[][]=new int[m+1][n+1];
		 int min[][] = new int[m+1][n+1]; 
		 for(int i=0;i<=n;i++) 
			 for(int j=0;j<=m;j++) 
				 min[j][i]='z'+1;
	    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	    for (int i=0; i<=m; i++) 
	    { 
	      for (int j=0; j<=n; j++)
	      { 
	        if (i == 0 || j == 0) 
	            L[i][j] = 0; 
	        else if (X[i-1] == Y[j-1]) { 
	            L[i][j] = L[i-1][j-1] + 1; 
	            ans[i][j]=ans[i-1][j-1]+X[i-1];
	         
	        }
	        else {
	            L[i][j] = max(L[i-1][j], L[i][j-1]); }
	      } 
	    } 
	  return L[m][n]; 
	  } 
	  
	  /* Utility function to get max of 2 integers */
	  int max(int a, int b) 
	  { 
	    return (a > b)? a : b; 
	  } 
 
     // Returns length of LCS for X[0..m-1], Y[0..n-1] 
     static String lcs(String X, String Y, int m, int n) 
     { 
         int[][] L = new int[m+1][n+1]; 
    
         // Following steps build L[m+1][n+1] in bottom up fashion. Note 
         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]  
         for (int i=0; i<=m; i++) 
         { 
             for (int j=0; j<=n; j++) 
             { 
                 if (i == 0 || j == 0) 
                     L[i][j] = 0; 
                 else if (X.charAt(i-1) == Y.charAt(j-1)) 
                     L[i][j] = L[i-1][j-1] + 1; 
                 else
                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]); 
             } 
         } 
    
         // Following code is used to print LCS 
         int index = L[m][n]; 
         int temp = index; 
    
         // Create a character array to store the lcs string 
         char[] lcs = new char[index+1]; 
         lcs[index] = '\u0000'; // Set the terminating character 
    
         // Start from the right-most-bottom-most corner and 
         // one by one store characters in lcs[] 
         int i = m; 
         int j = n; 
         while (i > 0 && j > 0) 
         { 
             // If current character in X[] and Y are same, then 
             // current character is part of LCS 
             if (X.charAt(i-1) == Y.charAt(j-1)) 
             { 
                 // Put current character in result 
                 lcs[index-1] = X.charAt(i-1);  
                   
                 // reduce values of i, j and index 
                 i--;  
                 j--;  
                 index--;      
             } 
    
             // If not same, then find the larger of two and 
             // go in the direction of larger value 
             else if (L[i-1][j] > L[i][j-1]) 
                 i--; 
             else
                 j--; 
         } 
    
         // Print the lcs 
         StringBuilder Sd=new StringBuilder();
         for(int k=0;k<=temp;k++) 
             Sd.append(lcs[k]); 
      return Sd.toString();   
     }
 }