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.lang.Math;
import java.io.* ;


public class Account {
	
	public static class Pair<Object1 ,Object2> {
	    Object1 key ;
	    Object2 val ;
	    
	    Pair(Object1 key ,Object2 val) {
	        this.key = key ;
	        this.val = val ;
	    }
	    
	    Pair() {}
	    
	}
	
	public static void main (String[] args) {
		
//		Scanner sc = new Scanner(System.in) ;
		FastReader sc = new FastReader() ;
//		StringBuilder res = new StringBuilder() ;
		int t= 1 ;  
		t = sc.nextInt() ;
		while(t-- > 0) {
			int n= sc.nextInt() ;
			long sml= 1 ;
			Set<Long> set = new HashSet<>() ;
			List<Long> list = new ArrayList<>() ;
			List<Long> rem = new ArrayList<>() ;
			long[] arr = new long[n] ;
			for(int i=0 ;i<n ;i++) {
				arr[i] = sc.nextLong() ;
			}
			Arrays.sort(arr);
			for(int i=0 ;i<n ;i++) {
				if(i > 0  &&  arr[i] == arr[i-1]) {
					list.add(arr[i]) ;
				}else if(arr[i] <=n  &&  arr[i] > 0  &&  set.contains(arr[i]) == false) {
					set.add(arr[i]) ;
				}else {
					list.add(arr[i]) ;
				}
			}for(long i=1 ;i<=n ;i++) {
				if(set.contains(i) == false) {
					rem.add(i) ;
				}
			}
			boolean flag = true ;
			int in = rem.size()-1 ,ans = rem.size() ;
//			System.out.println(rem+" "+list);
			for(int i=list.size()-1 ;i>=0 ;i--) {
				long x = rem.get(in) ;
				in-- ;
				if(x*2 >= list.get(i)) {
					flag = false ;
					break ;
				}
			}if(flag) {
				System.out.println(ans);
			}else {
				System.out.println("-1");
			}
  		}
	}
	
	
	/*
	 *   1--> a   3b   2c
	 *   2--> 2a  b    3c
	 *   3--> 3a  2b   c
	 */
		
	
	public static long gcd(long a, long b)
	{
	    if (b == 0)
	        return a;
	    return gcd(b, a % b);
	     
	}
	
	
//	_xor from 1 to n
	public static int xor(int n)
    {
        if (n % 4 == 0)
            return n;
      
        if (n % 4 == 1)
            return 1;
      
        if (n % 4 == 2)
            return n + 1;
      
        return 0;
    }

	
	public 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;
        }
 
        int [] readintarray(int n) {
            int res [] = new int [n];
            for(int i = 0; i<n; i++)res[i] = nextInt();
            return res;
        }
        long [] readlongarray(int n) {
            long res [] = new long [n];
            for(int i = 0; i<n; i++)res[i] = nextLong();
            return res;
        }
    }	
	
}