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.math.*;
	
	    public class Main {
	
	        // -- static variables --- //
	        static FastReader sc = new FastReader();
	        static PrintWriter out = new PrintWriter(System.out);
	        static int mod = (int) 1000000007;
	        public static void main(String[] args) throws Exception {
	         
	            int t=sc.nextInt();
	            while(t-->0)
	            Main.go();
	//             out.println();
	            out.flush();
	        }
	
	        // >>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<< //
	        static class pair{
	            int  x;int y;
	            pair(int  x,int y){
	                this.x=x;
	                this.y=y;
	            }
							@Override
							public int hashCode() {
								final int prime = 31;
								int result = 1;
								result = prime * result + x;
								result = prime * result + y;
								return result;
							}
							@Override
							public boolean equals(Object obj) {
								if (this == obj)
									return true;
								if (obj == null)
									return false;
								if (getClass() != obj.getClass())
									return false;
								pair other = (pair) obj;
								if (x != other.x)
									return false;
								if (y != other.y)
									return false;
								return true;
							}
	            
	        }


	        static void go() throws Exception {
	        	int n=sc.nextInt();
	        	int a[]=sc.intArray(n);
	        	sort(a);
	        	HashSet<Integer>set=new HashSet<>();
	        	for(int i:a) {
	        		set.add(i);	        	
	        		}
	        	int ans=0;
	        	TreeSet<Integer> set2=new TreeSet<>();
	        	TreeMap<Integer,Integer> aa = new TreeMap<>();
	        	for(int i=0;i<n;i++) {

	        			aa.put(a[i],aa.getOrDefault(a[i], 0)+1);

	        	}
	
	        	for(int i=0;i<n;i++) {
	        			if(set.contains(i+1)==false) {
	        				set2.add(i+1);
	        			}
	        	}
	        	int temp=aa.size();

	        	for(int i:set2) {
//	        		out.println(aa);
	        		if(aa.ceilingKey(i*2+1)==null) {
	        			out.println(-1);
	        			return;
	        		}else {
	        			int x=aa.ceilingKey(i*2+1);
//	        			out.println(x);
	        			if(aa.get(x)>0) {
	        				aa.put(x,aa.get(x)-1);
	        				if(aa.get(x)==0) {
	        					aa.remove(new Integer(x));
	        				}
	        			}else {
	        				out.println(-1);
	        				return;
	        			}
	        			ans++;
	        		}
	        	}
	        	out.println(ans);
	        

	        }
	        static long lcm(long a,long b) {
	        	return a*b/gcd(a,b);
	        }
	     
	    
	        // >>>>>>>>>>> Code Ends <<<<<<<<< //
	
	        // --For Rounding--//
	        static double round(double value, int places) {
	
	            if (places < 0)
	                throw new IllegalArgumentException();
	            BigDecimal bd = new BigDecimal(Double.toString(value));
	            bd = bd.setScale(places, RoundingMode.HALF_UP);
	            return bd.doubleValue();
	        }
	
	        // ----Greatest Common Divisor-----//
	        static long gcd(long a, long b) {
	            if (b == 0) {
	                return a;
	            }
	            return gcd(b, a % b);
	        }
	
	        // --- permutations and Combinations ---//
	        static long fact[];
	        static long invfact[];
	
	        static long ncr(int n, int k) {
	            if (k < 0 || k > n) {
	                return 0;
	            }
	            long x = fact[n];
	            long y = fact[k];
	            long yy = fact[n - k];
	            long ans = (x / y);
	            ans = (ans / yy);
	            return ans;
	        }
	
	        // ---sieve---//
	        static int prime[] = new int[1000006];
	
	        // static void sieve() {
	        //     Arrays.fill(prime, 1);
	        //     prime[0] = 0;
	        //     prime[1] = 0;
	        //     for (int i = 2; i * i <= 1000005; i++) {
	        //         if (prime[i] == 1)
	        //             for (int j = i * i; j <= 1000005; j += i) {
	        //                 prime[j] = 0;
	        //             }
	        //     }
	        // }
	
	        // ---- Manual sort ------//
	        static void sort(long[] a) {
	            ArrayList<Long> aa = new ArrayList<>();
	            for (long i : a) {
	                aa.add(i);
	            }
	            Collections.sort(aa);
	            for (int i = 0; i < a.length; i++)
	                a[i] = aa.get(i);
	        }
	
	
	        static void sort(int[] a) {
	            ArrayList<Integer> aa = new ArrayList<>();
	            for (int i : a) {
	                aa.add(i);
	            }
	            Collections.sort(aa);
	            for (int i = 0; i < a.length; i++)
	                a[i] = aa.get(i);
	        }
	
	        // --- Fast exponentiation ---//
	        static long pow(long x, long y) {
	            long res = 1l;
	            while (y != 0) {
	                if (y % 2 == 1) {
	                    res = (x * res)%mod;
	                }
	                y /= 2;
	                x = (x * x)%mod;
	            }
	            return res;
	        }
	
	        // >>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<< //
	        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());
	            }
	
	            int[] intArray(int n) {
	                int a[] = new int[n];
	                for (int i = 0; i < n; i++)
	                    a[i] = sc.nextInt();
	                return a;
	            }
	
	            long[] longArray(int n) {
	                long a[] = new long[n];
	                for (int i = 0; i < n; i++)
	                    a[i] = sc.nextLong();
	                return a;
	            }
	
	            String nextLine() {
	                String str = "";
	                try {
	                    str = br.readLine();
	                } catch (IOException e) {
	                    e.printStackTrace();
	                }
	                return str;
	            }
	        }
	    }