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

import java.io.*;
import java.util.*;



public class Test
{
    final static FastReader fr = new FastReader();
    final static PrintWriter out = new PrintWriter(System.out) ;
    static int mod = 1000000007;
    static long dp[][] ;

    static void solve()
    {
      int n  = fr.nextInt();

      int arr[] = new int[n] ;
      for (int i = 0 ; i < n ; i++) arr[i] = fr.nextInt();

      Arrays.sort(arr) ;

      TreeSet<Integer> rem = new TreeSet<>() ;
      for (int i = 1 ;  i <= n ; i++) rem.add(i) ;

      List<Integer> extras = new ArrayList<>() ;

      for (int i =0 ; i < n ; i++) {
          if (arr[i] > n){
              extras.add(arr[i]) ;
          } else {
              if (rem.contains(arr[i]))
              rem.remove(arr[i]) ;
          }
      }

      int i = 0 ;
      int ans = 0 ;

      if (extras.size() < rem.size()) {
          out.println(-1);
          return;
      }

      for (int x: rem)
      {
          int curr = x;
          if ((extras.get(i)-1)/2 < curr) {
              out.println(-1);
              return;
          }

          ans++ ;
          i++ ;
      }

      out.println(ans);



    }

    public static void main(String[] args)
    {
        int t =  fr.nextInt();

        while (t-- > 0)
        {
            solve() ;
        }
        out.close() ;
    }

    static class Pair{
        int x;
        int y ;

        Pair(int x, int y){
            this.x = x ;
            this.y= y ;
        }
    }

    static long gcd(long a, long b)
    {
        if (b == 0) return a ;
        return gcd(b,  a%b) ;
    }

    static long lcm(long a, long b)
    {
        long lcm = (a * b)/gcd(a, b) ;
        return lcm ;
    }

    static List<Integer> seive(int n)
    {
        // all are false by default
        // false -> prime, true -> composite
        boolean nums[] = new boolean[n+1] ;

        for (int i = 2 ; i <= Math.sqrt(n); i++)
        {
            if  (nums[i] == false)
            {
                for (int j = i*i ; j <= n ; j += i)
                {
                    nums[j] = true ;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();

        for (int i = 2 ; i <= n ;i++)
        {
            if (nums[i] == false) primes.add(i) ;
        }

        return primes ;
    }

    static boolean isVowel(char ch)
    {
        if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
            return true ;
        return false ;
    }

    static long fastpower(long a, long b)
    {
        long ans = 1 ;
        while (b > 0)
        {
            if ((b & 1) != 0) ans *= a ;
            a *= a  ;
            b >>= 1 ;
        }
        return ans ;
    }

    static int lower_bound(List<Long> arr, long key)
    {
        int pos = Collections.binarySearch(arr, key) ;
        if (pos < 0)
        {
            pos = - (pos + 1) ;
        }
        return pos ;
    }

    static int upper_bound(List<Long> arr, long key)
    {
        int pos = Collections.binarySearch(arr, key);
        pos++ ;
        if (pos < 0)
        {
            pos = -(pos) ;
        }
        return pos ;
    }

    static void printArr(int arr[])
    {
        int n = arr.length ;
        for (int i = 0 ; i < n ; i++) out.print(arr[i] + " ");
        out.println() ;
    }

    static class FastReader
    {

        BufferedReader br;

        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }


}