#include <bits/stdc++.h>
using namespace std;

int T;
vector<vector<int>> tests;   // mỗi bộ dữ liệu: n chữ số đã sắp xếp tăng dần

// Tổng của hai số có La và Lb chữ số (cho phép số 0 đứng đầu) khi chia các chữ số cho hai số.
// Cột thứ p (trọng số 10^p) có cnt chữ số. Đặt chữ số nhỏ vào cột có trọng số lớn trước
// (để tổng nhỏ nhất). Trả về tổng dưới dạng chuỗi (n <= 50 nên tổng có thể rất lớn).
string sumWithSplit(const vector<int> &dig, int La, int Lb) {
    int L = max(La, Lb);
    vector<long long> coef(L, 0);
    int idx = 0;
    for (int p = L - 1; p >= 0; p--) {
        int cnt = (p < La) + (p < Lb);     // số chữ số ở cột p
        for (int c = 0; c < cnt; c++) coef[p] += dig[idx++];
    }
    // cộng có nhớ để đổi các hệ số cột thành chuỗi thập phân
    vector<int> res;
    long long carry = 0;
    for (int p = 0; p < L; p++) {
        long long v = coef[p] + carry;
        res.push_back(v % 10);
        carry = v / 10;
    }
    while (carry) { res.push_back(carry % 10); carry /= 10; }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    string s;
    for (int i = (int)res.size() - 1; i >= 0; i--) s += char('0' + res[i]);
    return s;
}

// so sánh hai số dạng chuỗi (không có số 0 đứng đầu)
bool lessStr(const string &x, const string &y) {
    if (x.size() != y.size()) return x.size() < y.size();
    return x < y;
}

// Sub 1: vét cạn — thử mọi cách chia độ dài (La, Lb) với La + Lb = n, lấy tổng nhỏ nhất.
// Dùng khi mọi n <= 12
void sub1() {
    for (int t = 0; t < T; t++) {
        int n = tests[t].size();
        string best = "";
        bool has = false;
        for (int La = 0; La <= n; La++) {
            string cur = sumWithSplit(tests[t], La, n - La);
            if (!has || lessStr(cur, best)) { best = cur; has = true; }
        }
        cout << best << "\n";
    }
}

// Sub 2: chia đều: a có ceil(n/2) chữ số, b có floor(n/2) chữ số.
// Chia đều thì các trọng số 10^p xuất hiện ít nhất, nên tổng nhỏ nhất.
void sub2() {
    for (int t = 0; t < T; t++) {
        int n = tests[t].size();
        cout << sumWithSplit(tests[t], (n + 1) / 2, n / 2) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    tests.resize(T);
    bool small = true;
    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        tests[t].assign(n, 0);
        for (int i = 0; i < n; i++) cin >> tests[t][i];
        sort(tests[t].begin(), tests[t].end());
        if (n > 12) small = false;
    }
    if (small) sub1();   // n nhỏ: vét cạn các cách chia
    else sub2();         // n lớn: chia đều
    return 0;
}