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.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.util.*;



public class CF1 {

	static class FastScanner{	
		   private int BUFFER_SIZE = 1 << 16;
		   
		   private  DataInputStream din;
		   
		   private  byte[] buffer;
		   
		   private int bufferPointer, bytesRead;
		   
		   public FastScanner() {
		       din = new DataInputStream(System.in);
		       buffer = new byte[BUFFER_SIZE];
		       bufferPointer = bytesRead = 0;
		   }
		 
		   public FastScanner( String file_name) throws IOException {
		       din = new DataInputStream(new FileInputStream(file_name));
		       buffer = new byte[BUFFER_SIZE];
		       bufferPointer = bytesRead = 0;
		   }
		   
		   public String nextLine() throws IOException {
		        byte[] buf = new byte[64];
		       int cnt = 0, c;
		       while ((c = read()) != -1) {
		           if (c == '\n')
		               break;
		           buf[cnt++] = (byte) c;
		       }
		       return new String(buf, 0, cnt);
		   }
		   
		   public String next() throws IOException{
		 
		       byte c = read();
		       while(Character.isWhitespace(c)){
		           c = read();
		       }
		       
		        StringBuilder builder = new StringBuilder();
		       builder.append((char)c);
		       c = read();
		       while(!Character.isWhitespace(c)){
		           builder.append((char)c);
		           c = read();
		       }
		       
		       return builder.toString();
		   }
		 
		   public int nextInt() throws IOException {
		       int ret = 0;
		       byte c = read();
		       while (c <= ' ')
		           c = read();
		        boolean neg = (c == '-');
		       if (neg)
		           c = read();
		       do {
		           ret = ret * 10 + c - '0';
		       } while ((c = read()) >= '0' && c <= '9');
		 
		       if (neg)
		           return -ret;
		       return ret;
		   }
		   
		   public int[] nextIntArray( int n) throws IOException {
		        int arr[] = new int[n];
		       for(int i = 0; i < n; i++){
		           arr[i] = nextInt();
		       }
		       return arr;
		   }
		   public int[][] nextInt2DArray( int r,int c) throws IOException {
		      int arr[][] = new int[r][c];
		      for(int i = 0; i < r; i++){
		    	  for(int j=0;j < c; j++) {
		              arr[i][j] = nextInt();
		    	  }
		      }
		      return arr;
		  }
		   public int[][] nextInt2DArray(int n) throws IOException {
			      int arr[][] = new int[n][n];
			      for(int i = 0; i < n; i++){
			    	  for(int j=0;j < n; j++) {
			              arr[i][j] = nextInt();
			    	  }
			      }
			      return arr;
		   }
		   
		 
		   public long nextLong() throws IOException {
		       long ret = 0;
		       byte c = read();
		       while (c <= ' ')
		           c = read();
		        boolean neg = (c == '-');
		       if (neg)
		           c = read();
		       do {
		           ret = ret * 10 + c - '0';
		       } while ((c = read()) >= '0' && c <= '9');
		       if (neg)
		           return -ret;
		       return ret;
		   }
		   
		   public long[] nextLongArray( int n) throws IOException {
		        long arr[] = new long[n];
		       for(int i = 0; i < n; i++){
		           arr[i] = nextLong();
		       }
		       return arr;
		   }
		   public long[][] nextLong2DArray( int r,int c) throws IOException {
			      long arr[][] = new long[r][c];
			      for(int i = 0; i < r; i++){
			    	  for(int j = 0;j < c; j++) {
			              arr[i][j] = nextLong();
			    	  }
			      }
			      return arr;
			  }
		   public long[][] nextLong2DArray( int n) throws IOException {
			      long arr[][] = new long[n][n];
			      for(int i = 0; i < n; i++){
			    	  for(int j = 0;j < n; j++) {
			              arr[i][j] = nextLong();
			    	  }
			      }
			      return arr;
			  }
		 
		   public char nextChar() throws IOException{
		       byte c = read();
		       while(Character.isWhitespace(c)){
		           c = read();
		       }
		       return (char) c;	
		   }
		   public char[] nextCharArray(int n)throws IOException {
		       char arr[] = new char[n];
		      for(int i = 0; i < n; i++){
		          arr[i] = nextChar();
		      }
		      return arr;
		   }
		   public double nextDouble() throws IOException {
		       double ret = 0, div = 1;
		       byte c = read();
		       while (c <= ' ')
		           c = read();
		        boolean neg = (c == '-');
		       if (neg)
		           c = read();
		 
		       do {
		           ret = ret * 10 + c - '0';
		       } while ((c = read()) >= '0' && c <= '9');
		 
		       if (c == '.') {
		           while ((c = read()) >= '0' && c <= '9') {
		               ret += (c - '0') / (div *= 10);
		           }
		       }
		 
		       if (neg)
		           return -ret;
		       return ret;
		   }
		   
		   public double[] nextDoubleArray( int n) throws IOException {
		       double arr[] = new double[n];
		       for(int i = 0; i < n; i++){
		           arr[i] = nextDouble();
		       }
		       return arr;
		   }
		   public void printArray(int arr[]) {
			   for(int i=0;i<arr.length;i++) {
				   System.out.print(arr[i]+" ");
			   }
			   System.out.println();
		   }
		   private void fillBuffer() throws IOException {
		       bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
		       if (bytesRead == -1)
		           buffer[0] = -1;
		   }
		 
		   private byte read() throws IOException {
		       if (bufferPointer == bytesRead)
		           fillBuffer();
		       return buffer[bufferPointer++];
		   }
		 
		   public void close() throws IOException {
		       if (din == null)
		           return;
		       din.close();
		   }
			public boolean isPrime(int n) {
				if(n<2) return false;
				for(int i=2;i<=(int)Math.sqrt(n);i++) {
					if(n%i==0) return false;
				}
				return true;
			}
			public boolean isPrime(long n) {
				if(n<2) return false;
				for(long i=2;i<=(long)Math.sqrt(n);i++) {
					if(n%i==0) return false;
				}
				return true;
			}
			public boolean isCoPrime(int a,int b) {
				if(gcd(a,b)==1)return true;
				return false;
			}
			public boolean isCoPrime(long a,long b) {
				if(gcd(a,b)==1)return true;
				return false;
			}
			public boolean isPlaindrome(String S) {
			        for(int i=0;i<(S.length()/2);i++){
			            int x=S.length()-i-1;
			            if(S.charAt(i)!=S.charAt(x))return false;
			        }
			        return true;
			}
			public boolean[] sieve (int n) {
				boolean primes[]=new boolean[n+1];
				Arrays.fill(primes,true);
				primes[0]=primes[1]=false;
				for(int i=2;i*i<=n;i++){
					if(primes[i]){
						for(int j=i*i;j<=n;j+=i)
							primes[j]=false;
					}
				}
				return primes;
			}
			public long gcd(long a,long b){
				return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).longValue();
			}
			public int gcd(int a,int b){
				return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).intValue();
			}
			public int digits(int a){
				return (int) (Math.floor(Math.log10(a)) + 1);
			} 
			public long digits(long a){
				return (long) (Math.floor(Math.log10(a)) + 1);
			}
			public double log(int N,int b)
			{
				return(Math.log10(N)/Math.log10(b));
			}
			public double log(long N,long b)
			{
				return(Math.log10(N)/Math.log10(b));
			}
			public double log(double N,double b)
			{
				return(Math.log10(N)/Math.log10(b));
			}
			public boolean isPowerOfTwo (int x) 
			{ 
			      return (x!=0 && ((x&(x-1)) == 0));     
			}
			public void reverseArray(int ar[], int start, int end)
			{
				int temp;
				while(start<end)
				{
					temp = ar[start];
					ar[start]=ar[end];
					ar[end]=temp;
					start++;
					end--;
				}
			}
		    public int powerMod(int a,int N,int M) {
		        if (N == 0) {
		            return 1;
		        } else {
		            final int R = powerMod(a, N / 2, M);
		            if (N % 2 == 0) {
		                return (R * R) % M;
		            } else {
		                return (R * R * a) % M;
		            }
		        }
		    }
		    public long powerMod(long a,long N,long M) {
		        if (N == 0) {
		            return 1;
		        } else {
		            final long R = powerMod(a, N / 2, M);
		            if (N % 2 == 0) {
		                return (R * R) % M;
		            } else {
		                return (R * R * a) % M;
		            }
		        }
		    }
		}
	static FastScanner sc=new FastScanner();
	public static void main(String[] args) throws IOException {
		int t=sc.nextInt();
		while(t-->0){
			solve();
		}

	}
	private static void solve()throws IOException {
		int n=sc.nextInt();
		ArrayList<Integer> odd=new ArrayList<Integer>();
		ArrayList<Integer> even=new ArrayList<Integer>();
		for(int i=0;i<n;i++) {
			int num=sc.nextInt();
			if(num%2==0)
				even.add(num);
			else
				odd.add(num);
		}
//		int ol=odd.size();
//		int el=even.size();
		
//			if((ol%2==0)&&(el%2==0)) {
//				for(int i : odd) {
//					System.out.print(i+" ");
//				}
//				for(int i : even) {
//					System.out.print(i+" ");
//				}
//			}
//			else if((ol%2!=0)&&(el%2!=0)) {
//				for(int i=0;i<ol-1;i++) {
//					System.out.print(odd.get(i)+" ");
//				}
//				for(int i=0;i<el-1;i++) {
//					System.out.print(even.get(i)+" ");
//				}
//				System.out.println(odd.get(ol-1)+" "+even.get(el-1));
//			}
//			else if((ol%2==0)&&(el%2!=0)) {
//				for(int i=0;i<ol;i++) {
//					System.out.print(odd.get(i)+" ");
//				}
//				for(int i=0;i<el-1;i++) {
//					System.out.print(even.get(i)+" ");
//				}
//				System.out.println(even.get(el-1));
//			}
//			else {
//				for(int i=0;i<ol-1;i++) {
//					System.out.print(odd.get(i)+" ");
//				}
//				for(int i=0;i<el;i++) {
//					System.out.print(even.get(i)+" ");
//				}
//				System.out.println(odd.get(ol-1));
//			}
		for(int i:odd) {
			System.out.println(i+" ");
		}
		for(int i:even) {
			System.out.println(i+" ");
		}
		}
	

}