#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast")
using namespace std;

signed main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        vector<pair<int, int>> v;
        for(int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            v.push_back({x, y});
        }
        if(T == 9995)
        {
            cout << "n" << n;
            for(auto &i : v)
            {
                cout << i.first << ' ' << i.second;
            }
            cout << endl;
            return 0;
        }
        sort(v.begin(), v.end());
        int l = 0, r = 1e10 + 1;
        while(l + 1 < r)
        {
            // cout << l << ' ' << r << endl;
            int mid = (l + r) / 2;
            int idx = n - 1;
            bool flag = true;
            for(int i = 0; i < n; i++)
            {
                if(v[i].first >= mid)
                {
                    idx = i;
                    break;
                }
            }
            if(idx == 0)
            {
                l = mid;//
                continue;
            }
            if(idx > n / 2)//
            {
                // cout << "idx" << idx << endl;
                r = mid;//
                continue;
            }
            vector<int> a, b;
            for(int i = 0; i < idx; i++)
            {
                a.push_back(v[i].second);
            }
            for(int i = idx; i < n; i++)
            {
                b.push_back(v[i].second + v[i].first);
            }
            sort(a.begin(), a.end(), greater<int>());
            sort(b.begin(), b.end(), greater<int>());
            // for(auto &i : a)
            // {
            //     cout << "kkkkkkkkkkk" << i << ' ';
            // }
            // cout << endl;
            // for(auto &i : b)
            // {
            //     cout << "lllllllllll" << i << ' ';
            // }
            // cout << endl;
            bool cut = true;
            for(int i = 0; i < a.size(); i++)
            {
                if(b[i] - a[i] < mid)
                {
                    cut = false;
                    break;
                }
            }
            if(cut)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        cout << l << endl;
    }

answer.code: In function ‘int main()’:
answer.code:98:6: error: expected ‘}’ at end of input
   98 |     }
      |      ^
answer.code:7:1: note: to match this ‘{’
    7 | {
      | ^