#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N (100010)
#define inf (0x3f3f3f3f)
#define INF (0x3f3f3f3f3f3f3f3fll)
#define int long long
int T, n;
struct Data {
    int v, w;
    friend bool operator< (const Data& a, const Data& b) {
        return a.w < b.w;
    }
} P[N];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = getchar() : ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}

bool cmp(const Data& a, const Data& b) {
    return a.v < b.v;
}

bool check(int x) {
    priority_queue<Data> q1, q2;
    for (int i = 1; i <= n; ++i) {
        if (P[i].v < x) q1.push(P[i]);
        else q2.push(P[i]);
    }

    if (q1.size() > q2.size()) return false;
    while (q1.size() && q2.size()) {
        Data now = q1.top();
        bool flag = false;
        while (q2.size()) {
            Data tmp = q2.top(); q2.pop();
            if (tmp.w >= now.w) {
                flag = true;
                break;
            } 
            else if (tmp.v - (now.w - tmp.w) >= x) {
                flag = true;
                break;
            }
            else continue;
        }
        if (!flag) break;
        q1.pop();
    }
    return q1.empty();
}

signed main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; ++i) P[i].v = read(), P[i].w = read();
        sort(P + 1, P + n + 1, cmp);
        int l = P[1].v, r = P[n].v, mid, ans;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(mid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        printf("%lld\n", ans);
    }   
    return 0;
}