Paprika loves permutations. She has an array a_1, a_2, ..., a_n. She wants to make the array a permutation of integers 1 to n.

In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers i (1 ≤ i ≤ n) and x (x > 0), then perform a_i := a_i mod x (that is, replace a_i by the remainder of a_i divided by x). In different operations, the chosen i and x can be different.

Determine the minimum number of operations needed to make the array a permutation of integers 1 to n. If it is impossible, output -1.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 10^5).

The second line of each test case contains n integers a_1, a_2, ..., a_n. (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output the minimum number of operations needed to make the array a permutation of integers 1 to n, or -1 if it is impossible.

Example

Input


4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7


Output


1
-1
4
2

Note

For the first test, the only possible sequence of operations which minimizes the number of operations is: 

  * Choose i=2, x=5. Perform a_2 := a_2 mod 5 = 2. 



For the second test, it is impossible to obtain a permutation of integers from 1 to n.
8
2
2 3
3
3 4 5
1
1
1
2
1
3
1
4
1
12071207
5
5 5 5 9 14

1
2
0
-1
1
1
1
4

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long maxs = 1e5 + 5;
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
long long add(long long x, long long y) {
  long long res = x + y;
  return (res >= mod ? res - mod : res);
}
long long sub(long long x, long long y) {
  long long res = x - y;
  return (res <= 0 ? res + mod : res);
}
long long binpow(long long a, long long b) {
  a %= mod;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long mul(long long x, long long y) {
  long long res = x * y;
  return (res >= mod ? res % mod : res);
}
long long inv(long long x) { return binpow(x, mod - 2); }
template <class T>
long long size(T &a) {
  return a.size();
}
template <class T>
void read(vector<T> &a) {
  for (long long i = 0; i < size(a); i++) cin >> a[i];
}
long long ceil2(long long a, long long b) {
  if (a == 0) return 0;
  return (a + b - 1) / b;
}
inline long long maxim(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
inline long long minim(long long a, long long b) {
  if (a < b)
    return a;
  else
    return b;
}
inline bool equals(double a, double b) { return fabs(a - b) < 1e-9; }
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 64 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
long long allbit(long long n) { return (1LL << n) - 1; }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(long long i) { return i && (i & -i) == i; }
void extendgcd(long long a, long long b, long long *v) {
  if (b == 0) {
    v[0] = 1;
    v[1] = 0;
    v[2] = a;
    return;
  }
  extendgcd(b, a % b, v);
  long long x = v[1];
  v[1] = v[0] - v[1] * (a / b);
  v[0] = x;
  return;
}
template <class T>
class SegmentTree {
 public:
  SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  T query(int l, int r);
  void update(int idx, T val);

 private:
  T *tree;
  void buildTree(std::vector<T> data);
  int segTreeSize;
  T valueForExtraNodes;
  T (*combine)(T obj1, T obj2);
  int calculateSize(int n);
  T queryHelper(int l, int r, int st, int ed, int node);
};
template <class T>
SegmentTree<T>::SegmentTree(std::vector<T> data, T value,
                            T (*combine)(T obj1, T obj2)) {
  this->combine = combine;
  valueForExtraNodes = value;
  segTreeSize = calculateSize(data.size());
  buildTree(data);
}
template <class T>
SegmentTree<T>::SegmentTree(T ar[], int n, T value,
                            T (*combine)(T obj1, T obj2)) {
  this->combine = combine;
  valueForExtraNodes = value;
  segTreeSize = calculateSize(n);
  std::vector<T> data;
  for (int i = 0; i < n; i++) data.push_back(ar[i]);
  buildTree(data);
}
template <class T>
int SegmentTree<T>::calculateSize(int n) {
  int pow2 = 1;
  while (pow2 < n) {
    pow2 = pow2 << 1;
  }
  return 2 * pow2 - 1;
}
template <class T>
T SegmentTree<T>::query(int l, int r) {
  int st = 0, ed = segTreeSize / 2;
  return queryHelper(l, r, st, ed, 0);
}
template <class T>
T SegmentTree<T>::queryHelper(int l, int r, int st, int ed, int node) {
  if ((r < st) || (l > ed) || (l > r)) return valueForExtraNodes;
  if (st >= l && ed <= r) return tree[node];
  T leftVal = queryHelper(l, r, st, (st + ed) / 2, (2 * node + 1));
  T rightVal = queryHelper(l, r, (st + ed) / 2 + 1, ed, (2 * node + 2));
  return combine(leftVal, rightVal);
}
template <class T>
void SegmentTree<T>::buildTree(std::vector<T> data) {
  int n = data.size();
  tree = new T[segTreeSize];
  int extraNodes = (segTreeSize / 2 + 1) - n;
  for (int i = segTreeSize - 1; i >= 0; i--) {
    if (extraNodes > 0) {
      tree[i] = valueForExtraNodes;
      extraNodes--;
    } else if (n > 0) {
      tree[i] = data[n - 1];
      n--;
    } else
      tree[i] = combine(tree[(2 * i + 1)], tree[(2 * i + 2)]);
  }
}
template <class T>
void SegmentTree<T>::update(int idx, T val) {
  int segTreeIdx = (segTreeSize / 2) + idx;
  tree[segTreeIdx] = val;
  while (((segTreeIdx - 1) / 2) >= 0) {
    segTreeIdx = ((segTreeIdx - 1) / 2);
    if ((2 * segTreeIdx + 2) < segTreeSize)
      tree[segTreeIdx] =
          combine(tree[(2 * segTreeIdx + 1)], tree[(2 * segTreeIdx + 2)]);
    if (segTreeIdx == 0) break;
  }
}
vector<long long> primes(long long n) {
  bool prime[n + 1];
  vector<long long> p;
  fill_n(prime, n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (prime[i] == true) {
      for (int j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  for (int j = 2; j <= n; j++) {
    if (prime[j]) p.push_back(j);
  }
  return p;
}
const int N = 1000007;
int phi[N + 1];
void etf() {
  int n = N;
  phi[0] = 0;
  phi[1] = 1;
  for (int i = 2; i <= n; i++) phi[i] = i;
  for (int i = 2; i <= n; i++) {
    if (phi[i] == i) {
      for (int j = i; j <= n; j += i) phi[j] -= phi[j] / i;
    }
  }
}
vector<vector<int>> f(N);
void factors() {
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      f[j].push_back(i);
    }
  }
}
vector<long long> prime_factors(long long n) {
  vector<long long> p;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      p.push_back(i);
      n /= i;
    }
  }
  if (n > 1) {
    p.push_back(n);
  }
  return p;
}
int modInverse(int a, int m) {
  int m0 = m;
  int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    int q = a / m;
    int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
long long fact[200010];
void compute_fact(long long modVal) {
  fact[0] = 1;
  for (int i = 1; i <= 200004; i++) {
    fact[i] = (fact[i - 1] * i) % modVal;
  }
}
long long ncr_mod(long long n, long long r, long long modVal) {
  if (r == 0 || n == r) return 1;
  if (n < r) return 0;
  return (((fact[n] * modInverse(fact[r], modVal)) % modVal) *
          modInverse(fact[n - r], modVal)) %
         modVal;
}
long long findPreviousPowerOf2(long long n) {
  return 1LL << (long long)log2l(n);
}
long long previousPowerOfTwo(long long n) {
  if ((n && !(n & (n - 1LL))) == 1) {
    return (n >> 1LL);
  }
  while (n & n - 1LL) {
    n = n & n - 1LL;
  }
  return n;
}
long long nextPowerOfTwo(long long n) {
  long long value = 1LL;
  while (value <= n) {
    value = value << 1LL;
  }
  return value;
}
long long calprod(vector<long long> r) {
  long long res = 1;
  for (auto p : r) {
    res *= p;
  }
  return res;
}
int psq(int n) {
  if (sqrt(n) - floor(sqrt(n)) == 0) {
    return 1;
  }
  if (n <= 3) {
    return n;
  }
  int res = n;
  for (int i = 1; i <= n; i++) {
    int temp = i * i;
    if (temp > n)
      break;
    else
      res = min(res, 1 + psq(n - temp));
  }
  return res;
}
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);
  read(a);
  sort((a).begin(), (a).end());
  long long ans = 0;
  bool found = false;
  for (int i = 0; i < n; i++) {
    if (a[i] == i + 1) continue;
    int t = a[i] - (i + 1);
    if (a[i] % t == i + 1)
      ans++;
    else {
      found = true;
      break;
    }
  }
  if (found) {
    cout << "-1"
         << "\n";
  } else {
    cout << ans << "\n";
  }
}
int main() {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  cout << setprecision(6) << fixed;
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
