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 currentContest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;
import java.util.StringTokenizer;


public class P1 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader sc=new FastReader();
		int t=sc.nextInt();
		StringBuilder st=new StringBuilder();
		while(t--!=0){
			int n=sc.nextInt();
			int a[]=new int[n];
			int occ[]=new int[n+1];
			Arrays.fill(occ, 0);
			for(int i=0;i<n;i++) {
				a[i]=sc.nextInt();
				if(a[i]<=n) {
					occ[a[i]]++;
				}
			}
			ArrayDeque<Integer> tofind=new ArrayDeque<Integer>();
			for(int i=1;i<=n;i++) {
				if(occ[i]==0) {
					tofind.addLast(i);
				}
			}
			sort(a);
			int count=tofind.size();
			for(int i=n-1;i>=0;i--) {
				if(tofind.size()==0) {
					break;
				}
				if(a[i]>2*tofind.peekLast()&&tofind.peekLast()!=1) {
					a[i]=tofind.getLast();
					occ[tofind.getLast()]++;
					tofind.removeLast();
					occ[a[i]]--;
				}
			}
			if(tofind.size()>0&&tofind.peekLast()==1) {
				int get=0;
				for(int i=0;i<n;i++) {
					if(a[i]>n) {
						get=a[i];
						break;
					}else if(occ[a[i]]>1) {
						get=a[i];
						break;
					}
				}
				if(get!=2) {
					tofind.removeLast();
				}
			}
			if(tofind.size()==0)
			st.append(count+"\n");
			else
				st.append("-1\n");
		}
		System.out.println(st);
	}
	
	static class DisjointUnionSets {
		int[] rank, parent;
		int n;
		
		// Constructor
		public DisjointUnionSets(int n)
		{
			rank = new int[n];
			parent = new int[n];
			this.n = n;
			makeSet();
		}
		
		// Creates n sets with single item in each
		void makeSet()
		{
			for (int i = 0; i < n; i++) {
				// Initially, all elements are in
				// their own set.
				parent[i] = i;
			}
		}
		
		// Returns representative of x's set
		int find(int x)
		{
			// Finds the representative of the set
			// that x is an element of
			if (parent[x] != x) {
				// if x is not the parent of itself
				// Then x is not the representative of
				// his set,
				parent[x] = find(parent[x]);
				
				// so we recursively call Find on its parent
				// and move i's node directly under the
				// representative of this set
			}
			
			return parent[x];
		}
		
		// Unites the set that includes x and the set
		// that includes x
		void union(int x, int y)
		{
			// Find representatives of two sets
			int xRoot = find(x), yRoot = find(y);
			
			// Elements are in the same set, no need
			// to unite anything.
			if (xRoot == yRoot)
				return;
			
			// If x's rank is less than y's rank
			if (rank[xRoot] < rank[yRoot])
				
				// Then move x under y  so that depth
				// of tree remains less
				parent[xRoot] = yRoot;
			
			// Else if y's rank is less than x's rank
			else if (rank[yRoot] < rank[xRoot])
				
				// Then move y under x so that depth of
				// tree remains less
				parent[yRoot] = xRoot;
			
			else // if ranks are the same
			{
				// Then move y under x (doesn't matter
				// which one goes where)
				parent[yRoot] = xRoot;
				
				// And increment the result tree's
				// rank by 1
				rank[xRoot] = rank[xRoot] + 1;
			}
		}
	}

	static FastReader sc = new FastReader();

	public static void solvegraph() {
		int n = sc.nextInt();

		int edge[][] = new int[n - 1][2];
		for (int i = 0; i < n - 1; i++) {
			edge[i][0] = sc.nextInt() - 1;
			edge[i][1] = sc.nextInt() - 1;
		}
		ArrayList<ArrayList<Integer>> ad = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			ad.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < n - 1; i++) {
			ad.get(edge[i][0]).add(edge[i][1]);
			ad.get(edge[i][1]).add(edge[i][0]);
		}
		int parent[] = new int[n];
		Arrays.fill(parent, -1);
		parent[0] = n;
		ArrayDeque<Integer> queue = new ArrayDeque<>();
		queue.add(0);
		int child[] = new int[n];
		Arrays.fill(child, 0);
		ArrayList<Integer> lv = new ArrayList<Integer>();
		while (!queue.isEmpty()) {
			int toget = queue.getFirst();
			queue.removeFirst();
			child[toget] = ad.get(toget).size() - 1;
			for (int i = 0; i < ad.get(toget).size(); i++) {
				if (parent[ad.get(toget).get(i)] == -1) {
					parent[ad.get(toget).get(i)] = toget;
					queue.addLast(ad.get(toget).get(i));
				}
			}
			lv.add(toget);
		}

		child[0]++;
	}

	static void sort(int[] A) {
		int n = A.length;
		Random rnd = new Random();
		for (int i = 0; i < n; ++i) {
			int tmp = A[i];
			int randomPos = i + rnd.nextInt(n - i);
			A[i] = A[randomPos];
			A[randomPos] = tmp;
		}
		Arrays.sort(A);
	}
	static void sort(char[] A) {
		int n = A.length;
		Random rnd = new Random();
		for (int i = 0; i < n; ++i) {
			char tmp = A[i];
			int randomPos = i + rnd.nextInt(n - i);
			A[i] = A[randomPos];
			A[randomPos] = tmp;
		}
		Arrays.sort(A);
	}

	static void sort(long[] A) {
		int n = A.length;
		Random rnd = new Random();
		for (int i = 0; i < n; ++i) {
			long tmp = A[i];
			int randomPos = i + rnd.nextInt(n - i);
			A[i] = A[randomPos];
			A[randomPos] = tmp;
		}
		Arrays.sort(A);
	}

	static String sort(String s) {
		Character ch[] = new Character[s.length()];
		for (int i = 0; i < s.length(); i++) {
			ch[i] = s.charAt(i);
		}
		Arrays.sort(ch);
		StringBuffer st = new StringBuffer("");
		for (int i = 0; i < s.length(); i++) {
			st.append(ch[i]);
		}
		return st.toString();
	}

	public static long gcd(long a, long b) {
		if (a == 0) {
			return b;
		}
		return gcd(b % a, a);
	}

	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;
		}
	}
}
