#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}";
}
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")";
}
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif


unordered_map<ll, ll> graph;
unordered_set<ll> tr;
ll bound = 0;

bool pchaj(ll x) {
  if(x > bound)
    return false; 
  debug(x);
  if(!graph.count(x))
    return true;
  tr.insert(x);
  ll y = graph[x];
  ll i = 1;
  while(x - i * y > 0 || x + i * y <= bound) {
    ll lewy = x - i * y;
    ll prawy = x + i * y;
    debug(lewy, prawy);
    if(lewy > 0 && !tr.count(lewy) && pchaj(lewy)) {
      graph[lewy] = y;
      graph.erase(x);
      return 1;
    }
    if(prawy <= bound && !tr.count(prawy) && pchaj(prawy)) {
      graph[prawy] = y;
      graph.erase(x);
      return 1;
    }
    i++;
  }
  return 0;
}

void tc() {
  int n;
  cin >> n;
  vector<ll> ve(n);

  for(auto &i : ve)
    cin >> i; 

  sort(all(ve));
  reverse(all(ve));

  debug(ve);

  ll lo = 0, hi = (n + 1) * (*max_element(all(ve)) + 100);
  while(lo < hi - 1) {


    ll mid = (lo + hi) / 2;
    bound = mid;

    bool fail = 0;

    graph.clear();
    for(auto i : ve) {
      tr.clear();
      debug("push", i);
      if(!pchaj(i)) {
        debug("fail", i);
        fail = 1;
        break;
      }
      assert(!graph.count(i));
      graph[i] = i;
      debug(graph);
    }

    debug(mid, fail, graph);

    if(fail)
      lo = mid;
    else
      hi = mid;

  }

  cout << hi << endl;

}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int t;
  cin >> t;
  rep(i,0,t)
    tc();

}