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.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class C {

    private void solve() {
        int t = ri();
        while(t-- > 0) {
            int n = ri();
            int[] a = ria(n);
            a = sort(a);
            boolean flag = false;
            int count = 0;
            for(int i = 0; i < n; i++) {
                if(a[i] == i + 1) continue;
                if(a[i]%(a[i] - (i+1)) != i+1) {
                    flag = true;
                    break;
                }
                count++;
            }
            if(flag) {
                out.println(-1);
            } else {
                out.println(count);
            }
        }
    }

    //////////////////////////////////////////////////////////////////

    long sqrtLong(long x) {
        long root = (long) Math.sqrt(x);
        while (root * root > x) --root;
        while ((root + 1) * (root + 1) <= x) ++root;
        return root;
    }

    int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    int phi(int n) {
        int result = n;
        for (int i = 2; i * i <= n; ++i)
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        if (n > 1)
            result -= result / n;
        return result;
    }

    int factmod(int n, int p) {
        int res = 1;
        while (n > 1) {
            res = (res * ((n / p) % 2 == 1 ? p - 1 : 1)) % p;
            for (int i = 2; i <= n % p; ++i)
                res = (res * i) % p;
            n /= p;
        }
        return res % p;
    }

    int binpow(int a, int n) {
        int res = 1;
        while (n != 0) {
            if ((n & 1) != 0)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    String solPyatnashki() {
        int a[] = new int[16];
        for (int i = 0; i < 16; ++i)
            a[i] = ri();

        int inv = 0;
        for (int i = 0; i < 16; ++i)
            if (a[i] != 0)
                for (int j = 0; j < i; ++j)
                    if (a[j] > a[i])
                        ++inv;
        for (int i = 0; i < 16; ++i)
            if (a[i] == 0)
                inv += 1 + i / 4;


        return ((inv & 1) != 0 ? "No Solution" : "Solution Exists");
    }

    boolean isPrime(int number) {
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return number > 1;
    }

    boolean[] primes(int border) {
        boolean[] isPrimes = new boolean[border + 1];
        Arrays.fill(isPrimes, true);
        isPrimes[0] = false;
        isPrimes[1] = false;
        for (int i = 2; i < border + 1; i++) {
            if (!isPrimes[i]) continue;
            for (int k = i * 2; k < border; k += i) {
                isPrimes[k] = false;
            }
        }
        return isPrimes;
    }

    int[] sort(int[] arr) {
        Integer[] a = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        return arr;
    }

    long[] sort(long[] arr) {
        Long[] a = new Long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        return arr;
    }

    int max(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    long fastMod(String s1, long n2) {
        long num = 0;
        for (int i = 0; i < s1.length() - 1; i++) {
            num += Integer.parseInt(String.valueOf(s1.charAt(i)));
            num *= 10;
            if (num >= n2) {
                num = num % n2;
            }
        }
        return (num + Integer.parseInt(String.valueOf(s1.charAt(s1.length() - 1)))) % n2;
    }

    //////////////////////////////////////////////////////////////////

    private boolean yesNo(boolean yes) {
        return yesNo(yes, "YES", "NO");
    }

    private boolean yesNo(boolean yes, String yesString, String noString) {
        out.println(yes ? yesString : noString);
        return yes;
    }

    //////////////////////////////////////////////////////////////////

    private long rl() {
        return Long.parseLong(rs());
    }

    private double rd() {
        return Double.parseDouble(rs());
    }

    private int[] ria(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = ri();
        return a;
    }

    private int ri() {
        return Integer.parseInt(rs());
    }

    private String rs() {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) return null;
            tok = new StringTokenizer(nextLine);
        }

        return tok.nextToken();
    }

    private String readLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    //////////////////////////////////////////////////////////////////

    private BufferedReader in;
    private StringTokenizer tok;
    private PrintWriter out;

    private void initFileIO(String inputFileName, String outputFileName) throws FileNotFoundException {
        in = new BufferedReader(new FileReader(inputFileName));
        out = new PrintWriter(outputFileName);
    }

    private void initConsoleIO() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
    }

    private void initIO() throws IOException {
        Locale.setDefault(Locale.US);

        String fileName = "";

        if (!fileName.isEmpty()) {
            initFileIO(fileName + ".in", fileName + ".out");
        } else {
            if (new File("input.txt").exists()) {
                initFileIO("input.txt", "output.txt");
            } else {
                initConsoleIO();
            }
        }

        tok = new StringTokenizer("");
    }

    //////////////////////////////////////////////////////////////////

    private void run() {
        try {
            long timeStart = System.currentTimeMillis();

            initIO();
            solve();
            out.close();

            long timeEnd = System.currentTimeMillis();
            System.err.println("Time(ms) = " + (timeEnd - timeStart));
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
    }

    public static void main(String[] args) {
        new C().run();
    }

    ///////////////////////////////////////////////////////////////////
}
