#include<bits/stdc++.h>
using namespace std;
#define int long long
struct coin1 {
    int timer, pos;
};
struct vt {
    int first, second, third;
};
int n;
coin1 coin[1000006];

// Check if two robots can collect all coins with a maximum allowed movement range k
int check(int k) {
    vt robot[2];
    robot[0].first = robot[0].second = robot[0].third = 0;
    robot[1].first = robot[1].second = robot[1].third = 0;
    
    for (int i = 1; i <= n; i++) {
        if (robot[0].first == 0) {
            robot[0].second = coin[i].timer;
            robot[0].third = coin[i].pos + k;
            robot[0].first = coin[i].pos - k;
        } else if ((robot[0].first - (robot[0].second - coin[i].timer) * k) <= coin[i].pos && 
                   (robot[0].third + (robot[0].second - coin[i].timer) * k) >= coin[i].pos) {
            robot[0].first = max(coin[i].pos, robot[0].first - ((robot[0].second - coin[i].timer) * k));
            robot[0].third = min(coin[i].pos, robot[0].third + ((robot[0].second - coin[i].timer) * k));
            robot[0].second = coin[i].timer;
        } else if (robot[1].first == 0) {
            robot[1].third = coin[i].pos + k;
            robot[1].first = coin[i].pos - k;
            robot[1].second = coin[i].timer;
        } else if ((robot[1].first - (robot[1].second - coin[i].timer) * k) <= coin[i].pos && 
                   (robot[1].third + (robot[1].second - coin[i].timer) * k) >= coin[i].pos) {
            robot[1].first = max(coin[i].pos, robot[1].first - ((robot[1].second - coin[i].timer) * k));
            robot[1].third = min(coin[i].pos, robot[1].third + ((robot[1].second - coin[i].timer) * k));
            robot[1].second = coin[i].timer;
        } else {
            return 0;
        }
    }
    return 1;
}

// Comparator for sorting coins based on time and position
bool cmp(coin1 a, coin1 b) {
    if (a.timer != b.timer)
        return a.timer < b.timer;
    else 
        return a.pos < b.pos;
}

signed main() {
    int tc;
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> coin[i].timer >> coin[i].pos;
        }
        sort(coin + 1, coin + 1 + n, cmp);

        int l = 0, r = 1e9, res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid) == 1) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << res << "\n";
    }
    return 0;
}