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.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.AbstractMap;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.*;
import java.io.*;

// Java Template Pramod Hosahalli...
public class Solution {

	static FastReader in = new FastReader();
	//static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static int mod = 1000000007;

	private static void go() throws Exception {
		int n = in.ni();
		TreeSet<Integer> ts = new TreeSet<>();
		for(int i = 1; i <= n; i++) ts.add(i);

		List<Integer> fx = new ArrayList<>();
		for(int i = 0; i < n; i++){
			int val = in.ni();
			if(ts.contains(val)) ts.remove(val);
			else fx.add(val);
		}

		Collections.sort(fx, new Comparator<Integer>(){
			@Override
			public int compare(Integer x, Integer y){
				return Integer.compare(y,x);
			}
		});

		int count = 0;
		for(int i = 0; i < fx.size(); i++){
			int val = fx.get(i);
			if(!ts.isEmpty() && ts.last() * 2 < val){
				ts.remove(ts.last());
				count++;
			} 
		}

		if(ts.isEmpty()){
			print(1, count+"");
		}
		else print(1, "-1");
	}

		
	public static void main(String[] args) throws Exception {
		iterate();
	}
	
	private static void iterate() throws Exception {
		int t = in.ni();
		while(t-- > 0){
			go();
		}
		in.close();		
	}
	
	// matrix Exponentiation O(log n)
	private static double solve(long n, double[][] f)
	{
		double[][] res = new double[2][2];
		res[0][0] = 1;
		res[0][1] = 0;
		res[1][0] = 0;
		res[1][1] = 1;
		
		while(n > 0){
			if(n % 2 == 1) res = matrixmul(res,f);
			n = n >> 1;
			f = matrixmul(f, f);
		}
		return res[0][0];
	}

	private static long[][] matrixmul(long[][] a, long[][] b)
	{
		long[][] c = new long[2][2];
		for(int i = 0; i < 2; i++)
			for(int j = 0 ; j < 2; j++)
				for(int k = 0; k < 2; k++)
					c[i][k] = (c[i][k] + mul(a[i][j], b[j][k])) % mod; 
		return c;
	}

	private static double[][] matrixmul(double[][] a, double[][] b)
	{
		double[][] c = new double[2][2];
		for(int i = 0; i < 2; i++)
			for(int j = 0 ; j < 2; j++)
				for(int k = 0; k < 2; k++)
					c[i][k] = c[i][k] + a[i][j] *  b[j][k]; 
		return c;
	}

	static long mul(long a, long b) {
		return ((a % mod) * (b % mod)) % mod;
	}

	static class FastReader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public FastReader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastReader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public int[] rint(int n) throws IOException{
			int[] fx = new int[n];
			for(int i = 0; i < n; i++) fx[i] = ni();
			return fx;
		}

		public long[] rlong(int n) throws IOException {
			long[] fx = new long[n];
			for(int i = 0; i < n; i++) fx[i] = nl();
			return fx;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					if (cnt != 0) {
						break;
					} else {
						continue;
					}
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int ni() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nl() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nd() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	static String rl() throws Exception{
		return in.readLine();
	}

	static int pi(String s) {
		return Integer.parseInt(s);
	}

	static long pl(String s) {
		return Long.parseLong(s);
	}

	static void print(int newline, String s) {
		System.out.print(s);
		if (newline != 0) System.out.println();
		// System.out.flush();
	}

	static void print(int newline, int[] arr) {
		StringBuilder sb = new StringBuilder("");
		for(int x : arr) sb.append(x+" ");
		System.out.print(sb.toString().trim());
		if (newline != 0) System.out.println();
		// System.out.flush();
	}

	static void cprint(int x) {
		print(0, "Case #" + x + ": ");
	}

	//utility function for gcd
	private static long gcd(long a, long b)
	{
		if(a == 0 || b == 0)return a + b;
		if(a > b)return gcd(a % b, b);
		return gcd(a, b % a);
	}

	// construct sparse table : for static range queries
	static class SparseTable{
		static long[][] precompute(long[] arr)
		{
			int n = arr.length;
			int p = (int)((double)Math.log(n) / Math.log(2));
			long[][] f = new long[p+1][n];

			for(int i = 0; i < n; i++) f[0][i] = arr[i];
			for(int j = 1; j <= p; j++){
				for(int i = 0; i + (1 << j) - 1 < n; i++){
					f[j][i] = gcd(f[j-1][i], f[j-1][i + (1 << (j-1))]);
				}
			}
			return f;
		}
	}

	//Union Rank Algorithm
	static class UnionFind {
		int[] parent = null;
		int[] rank = null;

		UnionFind(int n){
			parent = new int[n];
			rank = new int[n];
			for(int i = 0; i < n; i++) parent[i] = i;
		}

		int find(int v){
			if(parent[v] != v) parent[v] = find(parent[v]);
			return parent[v];
		}

		boolean union(int x, int y) {
			int u = find(x);
			int v = find(y);

			//both belong to same set...
			if(u == v)return false;

			if(rank[u] > rank[v])
				parent[v] = u;
			else if(rank[u] < rank[v])
				parent[u] = v;
			else{
				parent[u] = v;
				rank[v]++;
			}
			return true;
		}
	}

	//Fenwick Tree Implementation
	static class BIT{
		int bit[] = null;

		BIT(int n){
			bit = new int[n+1];
		}

		private void update(int x){
			int index = x;
			while(index < bit.length){
				bit[index]+=1;
				index += (index & -index);
			}
		}

		private int sum(int l){
			int index = l-1;
			int c = 0;
			while(index > 0){
				c+=bit[index];
				index -= (index & -index);
			}
			return c;
		}
	}

	//Suffix Array Impl
	static class SuffixArray{

		// suffix array in O(n*log^2(n))
		public static Integer[] suffixArray(CharSequence s) {
			int n = s.length();
			Integer[] sa = new Integer[n];
			int[] rank = new int[n];
			for (int i = 0; i < n; i++) {
				sa[i] = i;
				rank[i] = s.charAt(i);
			}
			for (int len = 1; len < n; len *= 2) {
				long[] rank2 = new long[n];
				for (int i = 0; i < n; i++)
					rank2[i] = ((long) rank[i] << 32) + (i + len < n ? rank[i + len] + 1 : 0);

				Arrays.sort(sa, (a, b) -> Long.compare(rank2[a], rank2[b]));

				for (int i = 0; i < n; i++)
					rank[sa[i]] = i > 0 && rank2[sa[i - 1]] == rank2[sa[i]] ? rank[sa[i - 1]] : i;
			}
			return sa;
		}
	}

}