#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main() {
   //freopen("inp5.in", "r", stdin);
   //freopen("out5.out", "w", stdout);
   int t;
   cin >> t;
   while(t--) {
        int n;
        cin >> n;
        ll a[n];
        for(int i = 0; i < n; i++) cin >> a[i];
        ll score[2][2][2];
        memset(score, 0, sizeof(score));
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                priority_queue<ll> pq[2];
                for(int k = 0; k < n; k++) pq[a[k]&1].push(a[k]);
                int s1 = i, s2 = j;
                for(int k = 0; k < 2*n + 1; k++) {
                    if(k&1) {
                       if(!pq[s2].empty()) {
                            score[i][j][k&1] += pq[s2].top();
                            pq[s2].pop();
                            s2 = !s2;
                       }
                    } else {
                        if(!pq[s1].empty()) {
                            score[i][j][k&1] += pq[s1].top();
                            pq[s1].pop();
                            s1 = !s1;
                       }
                    }
                }
            }
        }
        ll sc[2];
        if(score[0][0][1] > score[0][1][1]) sc[0] = score[0][0][0];
        else if(score[0][0][1] < score[0][1][1]) sc[0] = score[0][1][0];
        else sc[0] = max(score[0][0][0], score[0][1][0]);
        if(score[1][0][1] > score[1][1][1]) sc[1] = score[1][0][0];
        else if(score[1][0][1] < score[1][1][1]) sc[1] = score[1][1][0];
        else sc[1] = max(score[1][0][0], score[1][1][0]);
        cout << max(sc[0], sc[1]) << "\n";
   }
}