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.lang.*;
import java.io.*;

public class Main {
    public static long mod = 1000000007;
    public static long mod2 = 998244353;
    static int N = 100050;
    static int[] lpf = new int[N];
    static int[] mobius = new int[N];

    public static void main(String[] args) throws java.lang.Exception {
        Reader sc = new Reader();
        FastNum in = new FastNum(System.in);
        PrintWriter out = new PrintWriter(System.out);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tests = in.nextInt();
        for (int test = 1; test <= tests; test++) {
            int n = in.nextInt();
            int[] a = new int[n];
            int[] c = new int[n+1];
            boolean[] b = new boolean[n+1];
            for (int i = 0; i < n; i++) a[i] = in.nextInt();
            for(int i : a) {
                if(i <= n) {
                    if(b[i]) {
                        c[i]++;
                    }
                    b[i] = true;
                }
                else {
                    int temp = i / 2;
                    if(temp <= n) c[i / 2]++;
                    else c[n]++;
                }
            }
            boolean f = true;
            int t = 0;
            int ans = 0;
            for(int i = n; i >= 1; i--) {
                if(!b[i]) {
                    t += c[i];
                    if(t <= 0) {
                        f = false;
                        break;
                    } else {
                        t--;
                        ans++;
                    }
                } else t += c[i];
            }
            if(f) out.println(ans);
            else out.println("-1");
        }


        out.flush();
    }



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

    public static long power(long a, long b) {
        if (b == 0)
            return 1;
        long answer = power(a, b / 2) % mod;
        answer = (answer * answer) % mod;
        if (b % 2 != 0)
            answer = (answer * a) % mod;
        return answer;
    }

    public static void swap(int x, int y) {
        int t = x;
        x = y;
        y = t;
    }

    public static long min(long a, long b) {
        if (a < b) return a;
        return b;
    }

    public static long divide(long a, long b) {
        return (a % mod * (power(b, mod - 2) % mod)) % mod;
    }

    public static long nCr(long n, long r) {
        long answer = 1;
        long k = min(r, n - r);
        for (long i = 0; i < k; i++) {
            answer = (answer % mod * (n - i) % mod) % mod;
            answer = divide(answer, i + 1);
        }
        return answer % mod;
    }

    public static boolean plaindrome(String str) {
        StringBuilder sb = new StringBuilder();
        sb.append(str);
        return (str.equals((sb.reverse()).toString()));
    }

    public static class Pair {
        int a;
        int b;

        Pair(int s, int e) {
            a = s;
            b = e;
        }
    }

    static class Assert {
        static void check(boolean e) {
            if (!e) {
                throw new AssertionError();
            }
        }
    }

    static class FastNum implements AutoCloseable {

        InputStream is;
        byte buffer[] = new byte[1 << 16];
        int size = 0;
        int pos = 0;

        FastNum(InputStream is) {
            this.is = is;
        }

        int nextChar() {
            if (pos >= size) {
                try {
                    size = is.read(buffer);
                } catch (IOException e) {
                    throw new IOError(e);
                }
                pos = 0;
                if (size == -1) {
                    return -1;
                }
            }
            Assert.check(pos < size);
            int c = buffer[pos] & 0xFF;
            pos++;
            return c;
        }

        int nextInt() {
            int c = nextChar();
            while (c == ' ' || c == '\r' || c == '\n' || c == '\t') {
                c = nextChar();
            }
            if (c == '-') {
                c = nextChar();
                Assert.check('0' <= c && c <= '9');
                int n = -(c - '0');
                c = nextChar();
                while ('0' <= c && c <= '9') {
                    int d = c - '0';
                    c = nextChar();
                    Assert.check(n > Integer.MIN_VALUE / 10
                            || n == Integer.MIN_VALUE / 10 && d <= -(Integer.MIN_VALUE % 10));
                    n = n * 10 - d;
                }
                return n;
            } else {
                Assert.check('0' <= c && c <= '9');
                int n = c - '0';
                c = nextChar();
                while ('0' <= c && c <= '9') {
                    int d = c - '0';
                    c = nextChar();
                    Assert.check(
                            n < Integer.MAX_VALUE / 10 || n == Integer.MAX_VALUE / 10 && d <= Integer.MAX_VALUE % 10);
                    n = n * 10 + d;
                }
                return n;
            }
        }

        @Override
        public void close() {
        }
    }


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

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

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

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

        public int nextInt() 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 nextLong() 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 nextDouble() 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();
        }
    }
}
