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

public class Main {
    private static ArrayList<Integer> A = new ArrayList<>();
    public static void main(String[] args) throws Exception{
        IO io = new IO(null, null);
        for (int T = io.getNextInt(); T > 0; T--) {
            int n = io.getNextInt();
            TreeMap<Integer, Integer> TM = new TreeMap<>();
            for (int i = 0; i < n; i++) {
                int x = io.getNextInt();
                if (!TM.containsKey(x)) {
                    TM.put(x, 0);
                }
                TM.put(x, TM.get(x) + 1);
            }
            A.clear();
            TreeSet<Integer> rem = new TreeSet<>();
            for (int i = 1; i <= n; i++) {
                if (TM.containsKey(i)) {
                    TM.put(i, TM.get(i) - 1);
                } else {
                    rem.add(i);
                }
            }
            for (int x : TM.keySet()) {
                int c = TM.get(x);
                for (;c > 0; c --) {
                    A.add(x);
                }
            }
            int ans = 0;
            int j = 0;
            for (int x : A) {
                int i = rem.pollFirst();
                if (x == i) continue;
                ans ++;
                if(i != x%(x - i)) {
                    ans = -1;
                    break;
                }
            }
            io.println(ans);
        }
        io.close();
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException {
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}

class pollardRho{
    private static BigInteger zero = new BigInteger("0");
    private static BigInteger one  = new BigInteger("1");
    private static BigInteger two  = new BigInteger("2");
    private static SecureRandom r = new SecureRandom();
    private static TreeMap<BigInteger, Integer> HM = new TreeMap<BigInteger, Integer>();

    public static TreeMap<BigInteger,Integer> factorize(BigInteger N) {
        HM.clear();
        factor(N);
        return new TreeMap<>(HM);
    }

    private static void factor(BigInteger N) {
        if (N.compareTo(one) == 0) return;
        if (N.isProbablePrime(20)) {
            if(!HM.containsKey(N))
                HM.put(N, 0);
            HM.put(N, HM.get(N) + 1);
            return;
        }
        BigInteger d = rho(N);
        factor(d);
        factor(N.divide(d));
    }

    private static BigInteger rho(BigInteger N) {
        BigInteger d;
        BigInteger c  = new BigInteger(N.bitLength(), r);
        BigInteger p  = new BigInteger(N.bitLength(), r);
        BigInteger q = p;

        if (N.mod(two).compareTo(zero) == 0) return two;

        d = one;
        while(d.compareTo(one) == 0) {
            p  =  p.multiply(p).mod(N).add(c).mod(N);
            q = q.multiply(q).mod(N).add(c).mod(N);
            q = q.multiply(q).mod(N).add(c).mod(N);
            d = p.subtract(q).gcd(N);
        }
        return d;
    }
}
