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 CPP):

Solution:
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
void solve();
int binaryConc(int x, int y);
string decToBinary(int n); 
int binaryToDecimal(string n);
string decToBinary(int n) 
{ 
string res = "";
int binaryNum[32]; 
int i = 0; 
while (n > 0) { 
binaryNum[i] = n % 2; 
n = n / 2; 
i++; 
} 
for (int j = i - 1; j >= 0; j--) 
res += (binaryNum[j]) ? '1' : '0';
return res;
} 
int binaryToDecimal(string n) 
{ 
string num = n; 
int dec_value = 0; 
int base = 1; 
int len = num.length(); 
for (int i = len - 1; i >= 0; i--) { 
if (num[i] == '1') 
dec_value += base; 
base = base * 2; 
} 
return dec_value; 
} 
int binaryConc(int x, int y)
{
string binx = decToBinary(x);
string biny = decToBinary(y);
string binXplusY = binx + biny;
string binYplusX = biny + binx;
int yplusx = binaryToDecimal(binYplusX);
int xplusy = binaryToDecimal(binXplusY);
return xplusy - yplusx;
}


string helper(int d, int s) 
{ 
string ans(d, '0'); 
for (int i = d - 1; i >= 0; i--) { 
if (s >= 9) { 
ans[i] = '9'; 
s -= 9; 
} 
else { 
char c = (char)s + '0'; 
ans[i] = c; 
s = 0; 
} 
} 
return ans; 
} 

// bool check(int x, int y, int k)
// {
//     int diff = abs(x)
//     if (abs(x - y) <= 2 * k && !((x ^ y) & 1))
//         return true;

//     return false;
// }
// void solve() {
//     deb("hi");
// }

// void sieve(int n, vector<int> &v, vector<bool> &prime)
// {
//     for (int i = 2; i * i <= n; i++)
//     {
//         if (prime[i])
//         {
//             for (int j = i * i; j <= n; j += i)
//                 prime[j] = 0;
//         }
//     }
//     for (int i = 2; i <= n; i++)
//     {
//         if (prime[i])
//         {
//             v.push_back(i);
//             // st.insert(i);
//         }
//     }
// }

int power(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

// void brute()
// {
//     int n, q, k;
//     cin >> n >> q >> k;
//     vector<int> a(n), v(n), pref(n + 1);
//     for (int i = 0; i < n; i++)
//         cin >> a[i];
//     for (int i = 0; i < n; i++)
//     {
//         if (i == 0)
//             v[i] = a[i + 1] - 2;
//         else if (i == n - 1)
//             v[i] = k - a[i];
//         // else if (i == 1)
//         //     v[i] = a[i] - 1;
//         else
//             v[i] = a[i + 1] - a[i - 1] - 2;
//     }
//     for (int i = 0; i < n; i++)
//         pref[i + 1] = v[i] + pref[i];

//     // deb(pref);
//     while (q--)
//     {
//         int l, r;
//         cin >> l >> r;
//         l--, r--;
//         int ans = 0;
//         if (l == r)
//         {
//             cout << k - 1 << "\n";
//             continue;
//         }
//         for (int i = l; i <= r; i++)
//         {
//             if (i == l)
//                 ans += a[i + 1] - 2;
//             else if (i == r)
//                 ans += k - a[i - 1] - 1;
//             else
//                 ans += a[i + 1] - a[i - 1] - 2;
//         }
//         cout << ans << "\n";
//     }
// }

void solve1()
{
    int n;
    cin >> n;
    vector<int> b(n + 2);
    set<int> st;
    for (int i = 0; i < n + 2; i++)
    {
        cin >> b[i];
        // st.insert(b[i]);
    }
    sort(b.begin(), b.end());
    // deb(b);
    int add = 0;
    for (int i = 0; i < n; i++)
        add += b[i];
    if (add == b[n]) 
    {
        for (int i = 0; i < n; i++)
            cout << b[i] << " ";
        cout << "\n";
    }
    else
    {
        add += b[n];
        int x = add - b[n + 1];
        for (int i = 0; i < n; i++)
            st.insert(b[i]);
        // deb(add, x);
        if (st.count(x))
        {
            bool f = 1;
            for (int i = 0; i < n + 1; i++)
            {
                if (b[i] == x)
                {
                    if (f)
                    {
                        f = 0;
                        continue;
                    }
                }
                cout << b[i] << " ";
            }
            cout << "\n";
        }
        else
            cout << "-1\n";
    }

}



void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), odd, even;
    // int even = 0, odd = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            odd.push_back(a[i]);
        else
            even.push_back(a[i]);
    }
    for (auto x : even)
        cout << x << " ";
    for (auto x : odd)
        cout << x << " ";
    cout << "\n";
}

int32_t main()
{
IOS;
int t = 1;
cin >> t;
int i = 1;
// sieve(1e6 + 5);
while (t--)
    {
        // sieve(2021);
        // cout << "Case #" << i << ": ";
solve();
        // brute();
i++;}
return 0;
}

// 
string findMin(int x, int Y) 
{ 
string y = to_string(Y); 
int n = y.size(); 
vector<int> p(n); 
for (int i = 0; i < n; i++) { 
p[i] = y[i] - '0'; 
if (i > 0) 
p[i] += p[i - 1]; 
} 
for (int i = n - 1, k = 0;; i--, k++) { 
int d = 0; 
if (i >= 0) 
d = y[i] - '0'; 
for (int j = d + 1; j <= 9; j++) { 
int r = (i > 0) * p[i - 1] + j; 
if (x - r >= 0 and x - r <= 9 * k) { 
string suf = helper(k, x - r); 
string pre = ""; 
if (i > 0) 
pre = y.substr(0, i); 
char cur = (char)j + '0'; 
pre += cur; 
return pre + suf; 
} 
} 
} 
}