#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}

long long P10(int x){
  return x == 0 ? 1 : 10 * P10(x - 1);
}

template <typename T, typename R = long long> 
vector<T> readArr(int len, R l, R r){
  vector<T> a(len);
  for(int i = 0; i < len; i++){
    if(i + 1 < len){
      a[i] = readIntSp(l, r);
    } else {
      a[i] = readIntLn(l, r);
    }
  }
  return a;
}

int main(){
  int t = readIntLn(1, 2 * P10(4));
  int sum_n = 0;
  while(t--){
    int n = readIntLn(1, P10(5));
    sum_n += n;
    auto A = readArr<int>(n, 1ll, P10(6));
    ll res = 0;
    for(int i = 0; i < 2; i++){
      vector<vector<ll>> got;
      for(int j = 0; j < 2; j++){
        priority_queue<int> pq[2];
        for(int k = 0; k < n; k++)
          pq[A[k] % 2].push(A[k]);
        vector<int> idx({i, j});
        vector<ll> score(2, 0ll);
        for(int t = 0, m = 0; m < 2 * n; m++, t ^= 1){
          if(!pq[idx[t]].empty()){
            score[t] += pq[idx[t]].top();
            pq[idx[t]].pop();
            idx[t] ^= 1;
          }
        }
        got.push_back(score);
      }
      if(got[0][1] < got[1][1] || (got[0][1] == got[1][1] && got[0][0] < got[1][0])){
        swap(got[0], got[1]);
      }
      res = max(res, got[0][0]);
    }
    cout << res << '\n';
  }
  assert(1 <= sum_n && sum_n <= 2 * P10(5));
  return 0;
}