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.util.*;
import java.io.*;
import java.lang.*;
public class codeforces {
   static int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;
    long maxl=Long.MAX_VALUE,minl=Long.MIN_VALUE;
    static PrintWriter pw = new PrintWriter(System.out);
    static StringBuilder sb=new StringBuilder();
    static int parent[] = new int[100001];
    static int mod = 1000000007;
    static boolean b1 = true;

    public static void main(String []args) {
        FastScanner sc = new FastScanner();

              int ttt = sc.nextInt();

              while (ttt-- > 0) {
                int n = sc.nextInt();

                int ar[] = new int[n+1];
                for(int i=1;i<=n;i++)
                    ar[i] = sc.nextInt();


                boolean b[] = new boolean[n+1];
                ArrayList<Integer> al = new ArrayList<>();

                for(int i=1;i<=n;i++){
                    if(ar[i]<=n&&!b[ar[i]]){
                        b[ar[i]] = true;
                    }
                    else
                        al.add(ar[i]);
                }
                Collections.sort(al);
                b1 = true;
                int j=0;
                for(int i=1;i<=n;i++){
                    if(!b[i]){
                        if(!(2*i<al.get(j)))
                        {
                            b1=false;
                            break;
                        }
                        else
                            j++;
                    }
                }
                if(b1)
                    pw.println(j);
                else
                    pw.println("-1");

               pw.flush();
    }


    }
    public static Boolean[] primeNo() {
        Boolean[] is_prime = new Boolean[1000001];
        int max = 1000000;
        for (int i = 2; i <= max; i++)
            is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; (long)i*i <= max; i++) {
            if (is_prime[i] == true) {
                for (int j = (i*i); j <= max; j += i)
                    is_prime[j] = false;
            }
        }
        return is_prime;
    }

    public static void union(int a,int b){
        parent[a] += parent[b];
        parent[b] = a;
    }
    public static int find(int a){
        if(parent[a]<0)
            return a;
        return (parent[a] =find(parent[a]));
    }

    public static class Pair{
        public  int x;
        public  int y;
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public static long gcd(long a,long b){
        if(a==0)
            return b;
        if(a>b){
            long k=b;
            b=a;
            a=k;
        }
        return gcd(b%a,a);
    }
    public static int binarySearch(long arr[],long x){
        int l=0,r=arr.length-1;
        int result1=-1;
        while(l<=r)
        {
            int mid = l+(r-l)/2;
            if(arr[mid]==x)
            {
                return mid;
            }
            else if(arr[mid]>x) {
                r = mid-1;
                result1 = r;
            }
            else {
                l = mid + 1;

            }
        }
        return result1;
    }
    public static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}