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

//package codeforces;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class solution{
	public static void main(String[] args){
		FastScanner s=new FastScanner();
    	PrintWriter out=new PrintWriter(System.out);
    	int t=s.nextInt();
    	for(int tt=0;tt<t;tt++) {
    		int n=s.nextInt();
    		long a[]=s.readLongArray(n);
    		HashMap<Long,Long> map=new HashMap<>();
    		for(int i=0;i<n;i++) {
    			map.put(a[i], 1+map.getOrDefault(a[i], (long)0));
    		}
    		ArrayList<Long> temp=new ArrayList<>(),temp2=new ArrayList<>();
    		for(long i=1;i<=(long)n;i++) {
    			if(!map.containsKey(i)) {
    				temp.add(i);
    			}
    		}
    		for(long i:map.keySet()) {
    			if(i<=(long)n) {
    				for(long j=0;j<map.get(i)-1;j++) {
						temp2.add(i);
					}
    			}else {
    				temp2.add(i);
    			}
    		}
    		Collections.sort(temp2);
    		int ans=temp.size();
    		for(int i=temp2.size()-1;i>=0;i--) {
    			if(temp.get(i)>temp2.get(i) || temp.get(i)>=(temp2.get(i)+1)/2) {
    				ans=-1;
    				break;
    			}
    		}
    		out.println(ans);
    	}
    	out.close();
    }
	public static void printb(boolean ans) {
		if(ans) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
	static boolean isPrime(int n){
        if (n <= 1)
            return false;
        else if (n == 2)
            return true;
        else if (n % 2 == 0)
            return false;
        for (int i = 3; i <= Math.sqrt(n); i += 2){
            if (n % i == 0)
                return false;
        }
        return true;
    }
	static long lcm(long a,long b){
	      return (a*b)/(gcd(a,b));
	    }
	static long gcd(long a, long b){
	      if (b == 0)
	        return a;
	      return gcd(b, a % b);
	    }
    static void sort(long [] a) {
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
    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 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();
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		boolean nextBoolean() {
			return Boolean.parseBoolean(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());
		}
		long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
	}
    static class Pair implements Comparable<Pair>{
    	int a,b; 
    	Pair(int a,int b){
    		this.a=a;
    		this.b=b;
    	}
    	public int compareTo(Pair o) {
    		if(b==o.b) {
    			return o.a-a;
    		}
    		return b-o.b;
    	}
    }
}
