#include < iostream>
#include < cstdio>
#include < cstdlib>
#include < cstring>
#include< algorithm>
#include< vector>
#define MAX_PEOPLE 100
#define MAX_WEIGHT 450
#define MAX_WEIGHT_SUM MAX_PEOPLE*MAX_WEIGHT
using namespace std;
int weights[MAX_PEOPLE];
bool** create2D(int x, int y){
bool **array = new bool*[x];
for (int i = 0; i < x; ++i){
` `array[i] = new bool[y];
memset(array[i], 0, sizeof(bool)*y);
}
return array;
}
void memset2D(int x, int y, bool **array) {
for(int i = 0; i < x; ++i)
memset(array[i], 0, sizeof(bool)*y);
}
int main(void) {
int n, N, W, maxDiff, teamWeight, temp,som;
int minWeight = MAX_WEIGHT, maxWeight = -1;
vector<double> minS;
vector<double> maxS;
cin >> N;
while(N--) {
cout<<"\n";
cin >> n;
W = 0;
for(int i = 0; i < n; ++i) {
cin >> weights[i];
if(weights[i] < minWeight)
minWeight = weights[i];
if(weights[i] > maxWeight)
maxWeight = weights[i];
W += weights[i];
}
int maxW = maxWeight + (W>>1);
int maxn = n>>1;
int index = 0;
bool **table = create2D(maxn+1, maxW+1);
table[0][0] = true;
for(int k = 0; k < n; ++k) {
for(int j = min(k, maxn) ; j >= 1; --j) {
for(int i = maxW; i >=minWeight ; --i) {
if (table[j][i] == false) {
index = i - weights[k];
if (index < 0) break;
table[j][i] = table[j-1][index];
}
}
}
}
maxDiff = MAX_WEIGHT_SUM ;
teamWeight = 0;
for(int i = 0; i <= maxW; ++i) {
if (table[n/2][i]) {
temp = abs(abs(W - i) - i);
if (temp < maxDiff) {
maxDiff = temp;
teamWeight = i;
}
}
}
teamWeight = min(teamWeight, W-teamWeight);
minS.push_back(teamWeight);
maxS.push_back(W - teamWeight);
}
for(som=0; som < minS.size()-1; ++som){
cout<< minS[som]<<"\t"<< maxS[som]<< endl;
cout<<"\n";
}
cout<< minS[som] << "\t"<< maxS[som]<< endl;
return 0;
}