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;

bool prime[10000007];
vector<int> primes;
void Sieve()
{
    int n = 100000;
 
    // In general Sieve of Sundaram, produces primes
    // smaller than (2*x + 2) for a number given
    // number x
    int nNew = sqrt(n);
 
    // This array is used to separate numbers of the
    // form i+j+2ij from others where  1 <= i <= j
    int marked[n/2+500] = {0};
 
    // eliminate indexes which does not produce primes
    for (int i=1; i<=(nNew-1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=n/2; j=j+2*i+1)
            marked[j] = 1;
 
    // Since 2 is a prime number
    primes.push_back(2);
 
    // Remaining primes are of the form 2*i + 1 such
    // that marked[i] is false.
    for (int i=1; i<=n/2; i++)
        if (marked[i] == 0)
            primes.push_back(2*i + 1);
}
void SieveOfEratosthenes()
{
  //bool prime[n + 1];
  memset(prime, true, sizeof(prime));

  for (int p = 2; p * p <= 10000007; p++)
  {
    if (prime[p] == true)
    {

      for (int i = p * p; i <= 10000007; i += p)
        prime[i] = false;
    }
  }
  // Print all prime numbers
  // for (int p = 2; p <= 10000007; p++)
  //     if (prime[p])
  //         cout << p << " ";
}

int binarySearch(int left,int right,int n)
{
    if (left<=right)
    {
        int mid = (left + right)/2;
 
        // base condition is, if we are reaching at left
        // corner or right corner of primes[] array then
        // return that corner element because before or
        // after that we don't have any prime number in
        // primes array
        if (mid == 0 || mid == primes.size()-1)
            return primes[mid];
 
        // now if n is itself a prime so it will be present
        // in primes array and here we have to find nearest
        // prime less than n so we will return primes[mid-1]
        if (primes[mid] == n)
            return primes[mid-1];
 
        // now if primes[mid]<n and primes[mid+1]>n that
        // mean we reached at nearest prime
        if (primes[mid] < n && primes[mid+1] > n)
            return primes[mid];
        if (n < primes[mid])
            return binarySearch(left, mid-1, n);
        else
            return binarySearch(mid+1, right, n);
    }
    return 0;
}

void solve()
{
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    sort(arr.begin(), arr.end());

    unordered_map<int, int> mp;
    vector<int> b;
    vector<int> unused;
    for(int i = 0; i < n; ++i)
    {
        int a = arr[i];
        // int b = (a-1)/2;
        mp[a]++;
        if(a > n)
        {
            unused.push_back(a);
        }
        else if(mp[a] == 2)
        {
            unused.push_back(a);
        }
        // mp[b+1]--;
    }
    sort(unused.begin(), unused.end());
    int index = 0;
    int ans = 0;
    // cout<<unused.size()<<endl;
    for(int i = 1; i <= n; ++i)
    {
        if(mp[i] == 0)
        {
            if(( (unused[index]-1)/2) < i)
            {
                cout<<-1<<endl;
                return;
            }
        else
        {
            ans++;
            index++;
        }
        }
    }
    cout<<ans<<endl;

    // int steps = 0;
    // int temp = 0;
    // for(int i = 1; i <= n; ++i)
    // {
    //     temp+=mp[i];
    //     if(temp == 0)
    //     {
    //         cout<<i<<endl;
    //         cout<<-1<<endl;
    //         return;
    //     }
    // }
    // for(int i = 1; i <= n; ++i)
    // {
    //     if(arr[i-1] != i)
    //     {
    //         steps++;
    //     }
    // }
    // cout<<steps<<endl;

    // int steps = 0;
    // for(int i = 1; i <= n; ++i)
    // {
    //     int a = arr[i-1];
    //     if(a==i || mp[i]>0)
    //     {
    //         // cout<<"hello";
    //         continue;
    //     }
    //     else if(((a-1)/2) < i)
    //     {
    //         cout<<-1<<endl;
    //         return;
    //     }
    //     else
    //     {
    //         steps++;
    //     }
    // }
    // cout<<steps<<endl;
}

int main() {
    // SieveOfEratosthenes();
    Sieve();
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}
