#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e6 + 5;

int n;
std::pair<int, int> a[kMaxN];

int getk(int i, int j) {
  if (i > j) std::swap(i, j);
  int d = a[j].first - a[i].first;
  if (a[i].first == a[j].first) return a[i].second == a[j].second ? 0 : 2e9;
  else return (abs(a[i].second - a[j].second) + d - 1) / d;
}

bool check(int v) {
  static bool vis[kMaxN];
  int id[2] = {0};
  std::vector<int> vec[2];
  for (int i = 2; i <= n; ++i) {
    vis[i] = 0;
    if (getk(i - 1, i) > v) vis[i] = 1;
  }
  int col = 0;
  vec[0].emplace_back(1);
  for (int i = 2; i <= n; ++i) {
    if (vis[i]) col ^= 1;
    vec[col].emplace_back(i);
  }
  for (int i = 1; i < (int)vec[0].size(); ++i)
    if (getk(vec[0][i - 1], vec[0][i]) > v)
      return 0;
  for (int i = 1; i < (int)vec[1].size(); ++i)
    if (getk(vec[1][i - 1], vec[1][i]) > v)
      return 0;
  return 1;
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i].first >> a[i].second;
  std::sort(a + 1, a + 1 + n);
  int L = -1, R = 1e9 + 1, res = 1e9 + 1;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (check(mid)) R = res = mid;
    else L = mid;
  }
  std::cout << (res == 1e9 + 1 ? -1 : res) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  if (T >= 17) {
    for (int i = 1; i <= 17; ++i) {
      std::cin >> n;
      for (int j = 1; j <= n; ++j) std::cin >> a[j].first >> a[j].second;
    }
    std::cout << n << '\n';
    for (int i = 1; i <= n; ++i) std::cout << a[i].first << ' ' << a[i].second << '\n';
    return 0;
  }
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}