// Author : hynu
// Problem : 

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

#if LOCAL
#include "algo/debug.h"
#endif

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int LIMIT = 1e6 + 7;
const ll INF = INT_MAX;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
vector<int> arr;

namespace subtask1 {    
    int res = INF;
    void backtrack(int p, ll a, ll b, ll c) {
        if (p == n) {
            res = min(res, (int)(max({a, b, c}) - min({a, b, c})));
            return;
        }

        backtrack(p + 1, a + arr[p], b, c);
        backtrack(p + 1, a, b + arr[p], c);
        backtrack(p + 1, a, b, c + arr[p]);
    }

    int solve() {
        backtrack(0, 0, 0, 0);
        return res;
    }
}

namespace subtask2 {    
    void gen(int l, int r, vector<array<ll, 3>>& vals) {
        int len = r - l;

        int total = 1;
        for (int i = 0; i < len; i++) total *= 3;

        for (int mask = 0; mask < total; ++mask) {
            int m = mask;
            ll a, b, c;
            a = b = c = 0;

            for (int i = 0; i < len; ++i) {
                int r = m % 3;
                m /= 3;

                int val = arr[l + i];
                if (r == 0) a += val;
                if (r == 1) b += val;
                if (r == 2) c += val;
            }
            vals.push_back({a, b, c});
        }
    }


    void prune(vector<array<ll, 3>>& vals) {
        sort(vals.begin(), vals.end(), [](auto &x, auto &y) {
            if (x[0] != y[0]) return x[0] < y[0];
            if (x[1] != y[1]) return x[1] < y[1];
            return x[2] < y[2];
        });

        map<ll, ll> front;
        vector<array<ll, 3>> res;

        for (auto [a, b, c] : vals) {
            auto it = front.lower_bound(b);
            bool found = false;

            if (it != front.begin()) {
                --it;
                if (it->second <= c) found = true;
            }

            if (found) continue;

            while (it != front.end() && it->second >= c) it = front.erase(it);

            front[b] = c;
            res.push_back({a, b, c});
        }

        vals = res;
        return;
    }

    ll solve() {
        int res = INF;
        vector<array<ll, 3>> v1, v2;
        
        gen(0, n >> 1, v1);
        gen(n >> 1, n, v2);
        prune(v1); 
        prune(v2);

        for (auto [a1, b1, c1] : v1) {
            for (auto [a2, b2, c2] : v2) {
                ll a = a1 + a2;
                ll b = b1 + b2;
                ll c = c1 + c2;

                res = min(res, (int)(max({a, b, c}) - min({a, b, c})));
            }
        }

        return res;  
    }
}

namespace subtask3 {
    //dp
}



class stress {
private: 
    int rnd(int l, int r) {
        return uniform_int_distribution<int>(l, r)(rng);
    }
public:
    stress(int t, int n) {
        bool accept = true;
        while (t--) {
            arr.assign(n, 0);
            for (int& val : arr) val = rnd(1, 1e6);

            int res1 = subtask1::solve();
            int res2 = subtask1::solve();

            if (res1 != res2) {
                cout << n << '\n';
                for (int val : arr) cout << val << ' ';
                accept = false;
                return;
            }
        }
        if (accept) cout << "passed!";
    }
};

signed main() { 
    cin.tie(nullptr), cout.tie(nullptr) -> ios_base::sync_with_stdio(false);

    #define task "sol"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin), freopen(task".out", "w", stdout);
    }

    /*
    cin >> n;
    arr.resize(n);

    for (int& val : arr) cin >> val;

    subtask2::solve();
    */

    int t;
    cin >> t;

    stress(t, 10);

    return 0;
}