#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define w(i) T[(i)].w
#define ls(i) T[(i)].ls
#define rs(i) T[(i)].rs
const int MAXN(2e3+7);

int N, T;
struct nd {
    ll x, y, w;
}pepo[MAXN];
ll xx[MAXN], yy[MAXN];
int cntx, cnty;
ll ynum[MAXN];
ll outt;

ll mxx[MAXN << 2], lmx[MAXN << 2], rmx[MAXN << 2], smm[MAXN << 2];
inline void PushUp(int rt) {
    smm[rt] = smm[rt<<1]+smm[rt<<1|1];
    lmx[rt] = max(lmx[rt<<1], smm[rt<<1]+lmx[rt<<1|1]);
    rmx[rt] = max(rmx[rt<<1|1], rmx[rt<<1]+smm[rt<<1|1]);
    mxx[rt] = max(mxx[rt << 1], mxx[rt << 1 | 1]);
    mxx[rt] = max(mxx[rt], rmx[rt<<1]+lmx[rt<<1|1]);
}
inline void Build(int l, int r, int rt) {
    if (l == r) {
        mxx[rt] = lmx[rt] = rmx[rt] = smm[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
    PushUp(rt);
}
inline void Add(int L, ll C, int l, int r, int rt) {
    if (l == r) {
        lmx[rt] = rmx[rt] = mxx[rt] = smm[rt] = smm[rt] + C;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) { Add(L, C, l, mid, rt << 1); }
    else { Add(L, C, mid + 1, r, rt << 1 | 1); }
    PushUp(rt);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--) {
        outt = 0;
        cin >> N;
        //离散化
        per(i, 1, N+1) { cin>>pepo[i].x>>pepo[i].y>>pepo[i].w; xx[i]=pepo[i].x, yy[i]=pepo[i].y; }
        sort(xx+1, xx+1+N, [](const ll& i, const ll& j) {return i<j;});
        sort(yy+1, yy+1+N, [](const ll& i, const ll& j) {return i<j;});
        cntx = unique(xx+1, xx+1+N)-xx;
        cnty = unique(yy+1, yy+1+N)-yy;
        per(i, 1, N+1) {
            pepo[i].x = lower_bound(xx+1, xx+cntx, pepo[i].x)-xx;
            pepo[i].y = lower_bound(yy+1, yy+cnty, pepo[i].y)-yy;
        }
        //离散化结束

        if(cntx<cnty) {
            sort(pepo+1, pepo+1+N, [](const nd& i, const nd& j) { return i.x==j.x?i.y<j.y:i.x<j.x; });
            int pepcntup = 1, pepcntdwn;
            per(up, 1, cntx) {
                Build(1, cnty-1, 1);
                while (pepcntup <= N && pepo[pepcntup].x <= up) {
                    nd tmpp = pepo[pepcntup++];
                    Add(tmpp.y, tmpp.w, 1, cnty-1, 1);
                }
                pepcntdwn = pepcntup;
                per(dn, up, cntx) {
                    while (pepcntdwn <= N && pepo[pepcntdwn].x <= dn) {
                        nd tmpp = pepo[pepcntdwn++];
                        Add(tmpp.y, tmpp.w, 1, cnty-1, 1);
                    }
                    outt = max(outt, mxx[1]);
                }
            }
        } else {
            sort(pepo+1, pepo+1+N, [](const nd& i, const nd& j) { return i.y==j.y?i.x<j.x:i.y<j.y; });
            int pepcntup = 1, pepcntdwn;
            per(up, 1, cnty) {
                Build(1, cntx-1, 1);
                while (pepcntup <= N && pepo[pepcntup].y <= up) {
                    nd tmpp = pepo[pepcntup++];
                    Add(tmpp.x, tmpp.w, 1, cntx-1, 1);
                }
                pepcntdwn = pepcntup;
                per(dn, up, cntx) {
                    while (pepcntdwn <= N && pepo[pepcntdwn].y <= dn) {
                        nd tmpp = pepo[pepcntdwn++];
                        Add(tmpp.x, tmpp.w, 1, cntx-1, 1);
                    }
                    outt = max(outt, mxx[1]);
                }
            }
        }
        cout << outt << '\n';
    }

    return 0;
}

#pragma warning(disable:4996)

#include<bits/stdc++.h>
#define upf(a,b,c) for(ll a=b;a<=c;++a)
#define drf(a,b,c) for(ll a=b;a>=c;--a)
#define ll long long
#define mod MOD
const int MOD(998244353);
const double esp(1e-6);
const int maxn(1e5+5);
using namespace std;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll m, k, T;
int main()
{
#ifdef ACM_LOCAL
    freopen("./ACM.in", "r", stdin);
    freopen("./ACM.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    while (T--) {
        cin >> k >> m;
        ll sum; 
        ll n;
        int flag = 0;
        if (k > 1720) {
            n = k - k % 1720;
        }
        else {
            n = 1;
        }
        upf(i, n, k + 1720) {
            ll tmp = k ^ i;
            sum = 0;
            ll pos;
            upf(j, 1, 100000) {
                if (gcd(i, i + j) == 1) {
                    sum++;
                }
                if (sum == m) {
                    pos = j;
                    break;
                }
            }
            if (pos == tmp) {
                cout << i << endl;
                flag = 1;
                break;
            }
        }
        if (!flag) {
            cout << -1 << endl;
        }
    }
}

#include<bits/stdc++.h>
#define FIN freopen("./1012.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll T,n,ans_S,ans_E,del;
struct node{
    int key,flag,index;
    bool operator<(const node &a)const {
        return key<a.key;
    }
}h[maxn],tmp;
priority_queue<node> p;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        ans_S=ans_E=del=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>h[i].key;
            h[i].flag=1;
            h[i].index=i;
        }
        for(int i=n/2+1;i<=n;i++){
            p.push(h[i]);
        }
        while(del<n){
            tmp=p.top();
            del++;
            if(del%2){
                ans_S+=tmp.key;
            }else{
                ans_E+=tmp.key;
            }
            h[tmp.index].flag=0;
            int par=tmp.index/2;
            if(h[par*2].flag==0&&h[par*2+1].flag==0){
                p.push(h[par]);
            }
            p.pop();
        }
        cout<<ans_S<<" "<<ans_E<<"\n";
    }
}