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.math.*;
import java.util.* ;

import java.io.* ;
@SuppressWarnings("unused")
//i am working for the day i will surpass you
//Scanner in = new Scanner(new File("i.txt"));
//in.close();
//PrintWriter writer = new PrintWriter("o.txt");
//writer.close();
 
public class A
{
	static final int mod = (int)1e9+7 ;
	static final double pi = 3.1415926536 ;
	static boolean not_prime[] = new boolean[10000001] ;
	static void sieve() {
		for(int i=2 ; i*i<10000001 ; i++) {
			if(not_prime[i]==false) {
				for(int j=2*i ; j<10000001 ; j+=i) {
					not_prime[j]=true ;
				}
			}
		}not_prime[0]=true ; not_prime[1]=true ;
	}		
	public static long bexp(long base , long power)
	{
		long res=1L ;
		
		base = base%mod ;
		
		while(power>0) {
			if((power&1)==1) {
				res=(res*base)%mod ;
				power-- ;
			}
			else {
				base=(base*base)%mod ;
				power>>=1 ;
			}
		}
		
		return res ;
	}
	static long modInverse(long n, long p){return power(n, p - 2, p); }
	static long power(long x, long y, long p)
	{
	  
	    // Initialize result
	    long res = 1;
	    x = x % p;
	  
	    while (y > 0) {
	  
	        if (y % 2 == 1)
	            res = (res * x) % p;
	        
	        y = y >> 1;
	        x = (x * x) % p;
	    }
	  
	    return res;
	}
	static long nCrModPFermat(int n, int r, long p){if(n<r) return 0 ;if (r == 0)return 1; long[] fac = new long[n + 1];fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i % p;return (fac[n] * modInverse(fac[r], p) % p* modInverse(fac[n - r], p) % p) % p;}	
	static long modular_add(long a, long b){ return ((a % mod) + (b % mod)) % mod; }
	static long modular_sub(long a, long b){ return ((a % mod) - (b % mod) + mod) % mod; }
	static long modular_mult(long a, long b){ return ((a % mod) * (b % mod)) % mod; }	
	static long lcm(long f, long f2){ return (f / gcd(f, f2)) * f2; }
	static long gcd(long a, long b){if (b == 0) {return a;}return gcd(b, a % b);}
	static int cbits(long x) {return (int)(Math.log(x)/Math.log(2)+1) ;}
	
	public static void main(String[] args)throws Exception
    {
		FastReader in = new FastReader() ;
		StringBuilder op = new StringBuilder() ;
		int T = in.nextInt(); 
	//	int T=1 ;
		for(int tt=0 ; tt<T ; tt++){
			
			int n = in.nextInt() ;
			int a[] = in.readArray(n) ;
			sort(a) ;
			int check[] = new int[n+1] ;
			List<Integer> greater = new ArrayList<>() ;
			for(int el : a) {
				if(el > n || check[el]==1)greater.add(el) ;
				else check[el]=1 ;
			}
			List<Integer> req = new ArrayList<>() ;
			for(int i=1 ; i<=n ; i++) {
				if(check[i]==0)req.add(i) ;
			}
		//	System.out.println(req+" "+greater);
			int f=0 , c=0 ;
			for(int i=0 ; i<req.size() ; i++) {
				int reqEl = req.get(i) ;
				int gre = greater.get(i) ;
				int range = ((gre&1)==1)?gre/2 : (gre-1)/2 ;
				if(reqEl>range) {
					f=1 ;
					break ;
				}
				 c++ ;
				 check[reqEl]=1 ;
			}
			if(f==0)op.append(c+"\n") ;
			else op.append("-1\n") ;
		}
		System.out.println(op.toString());
    }
	

	static class pair implements Comparable<pair>
	{
		int first , second ;
		pair(int first , int second){
			this.first=first ;
			this.second=second; 
		}
		public int compareTo(pair other) {
			return this.second-other.second ;
		}
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	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[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
    }

}