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.*;
import java.util.concurrent.ThreadLocalRandom;
import java.math.*;

/**
 __                  __
 ( _)                ( _)
 / / \\              / /\_\_
 / /   \\            / / | \ \
 / /     \\          / /  |\ \ \
 /  /   ,  \ ,       / /   /|  \ \
 /  /    |\_ /|      / /   / \   \_\
 /  /  |\/ _ '_| \   / /   /   \    \\
 |  /   |/  0 \0\    / |    |    \    \\
 |    |\|      \_\_ /  /    |     \    \\
 |  | |/    \.\ o\o)  /      \     |    \\
 \    |     /\\`v-v  /        |    |     \\
 | \/    /_| \\_|  /         |    | \    \\
 | |    /__/_ `-` /   _____  |    |  \    \\
 \|    [__]  \_/  |_________  \   |   \    ()
 /    [___] (    \         \  |\ |   |   //
 |    [___]                  |\| \|   /  |/
 /|    [____]                  \  |/\ / / ||
 (  \   [____ /     ) _\      \  \    \| | ||
 \  \  [_____|    / /     __/    \   / / //
 |   \ [_____/   / /        \    |   \/ //
 |   /  '----|   /=\____   _/    |   / //
 __ /  /        |  /   ___/  _/\    \  | ||
 (/-(/-\)       /   \  (/\/\)/  |    /  | /
 (/\/\)           /   /   //
 _________/   /    /
 \____________/    (


 @author NTUDragons-Reborn
 */

public class C{
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
    // main solver
    static class Task{

        double eps= 0.00000001;
        static final int MAXN = 200015;
        static final int MOD= 998244353;

        // stores smallest prime factor for every number
        static int spf[] = new int[MAXN];

        static boolean[] prime;

        Map<Integer,Set<Integer>> dp= new HashMap<>();

        // Calculating SPF (Smallest Prime Factor) for every
        // number till MAXN.
        // Time Complexity : O(nloglogn)
        public void sieve()
        {
            spf[1] = 1;
            for (int i=2; i<MAXN; i++)

                // marking smallest prime factor for every
                // number to be itself.
                spf[i] = i;

            // separately marking spf for every even
            // number as 2
            for (int i=4; i<MAXN; i+=2)
                spf[i] = 2;

            for (int i=3; i*i<MAXN; i++)
            {
                // checking if i is prime
                if (spf[i] == i)
                {
                    // marking SPF for all numbers divisible by i
                    for (int j=i*i; j<MAXN; j+=i)

                        // marking spf[j] if it is not
                        // previously marked
                        if (spf[j]==j)
                            spf[j] = i;
                }
            }
        }

        void sieveOfEratosthenes(int n)
        {
            // Create a boolean array
            // "prime[0..n]" and
            // initialize all entries
            // it as true. A value in
            // prime[i] will finally be
            // false if i is Not a
            // prime, else true.
            prime= new boolean[n + 1];
            for (int i = 0; i <= n; i++)
                prime[i] = true;
    
            for (int p = 2; p * p <= n; p++)
            {
                // If prime[p] is not changed, then it is a
                // prime
                if (prime[p] == true)
                {
                    // Update all multiples of p
                    for (int i = p * p; i <= n; i += p)
                        prime[i] = false;
                }
            }
        }

        // A O(log n) function returning primefactorization
        // by dividing by smallest prime factor at every step
        public Set<Integer> getFactorization(int x)
        {
            if(dp.containsKey(x)) return dp.get(x);
            Set<Integer> ret = new HashSet<>();
            while (x != 1)
            {
                if(spf[x]!=2) ret.add(spf[x]);
                x = x / spf[x];
            }
            dp.put(x,ret);
            return ret;
        }
        // function to find first index >= x
        public int lowerIndex(List<Integer> arr, int n, int x)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr.get(mid) >= x)
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }
        public int lowerIndex(int[] arr, int n, int x)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr[mid] >= x)
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }

        // function to find last index <= y
        public int upperIndex(List<Integer> arr, int n, int y)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr.get(mid) <= y)
                    l = mid + 1;
                else
                    h = mid - 1;
            }
            return h;
        }
        public int upperIndex(int[] arr, int n, int y)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr[mid] <= y)
                    l = mid + 1;
                else
                    h = mid - 1;
            }
            return h;
        }

        // function to count elements within given range
        public int countInRange(List<Integer> arr, int n, int x, int y)
        {
            // initialize result
            int count = 0;
            count = upperIndex(arr, n, y) -
                    lowerIndex(arr, n, x) + 1;
            return count;
        }

        public int add(int a, int b){
            a+=b;
            while(a>=MOD) a-=MOD;
            while(a<0) a+=MOD;
            return a;
        }

        public int mul(int a, int b){
            long res= (long)a*(long)b;
            return (int)(res%MOD);
        }

        public int power(int a, int b) {
            int ans=1;
            while(b>0){
                if((b&1)!=0) ans= mul(ans,a);
                b>>=1;
                a= mul(a,a);
            }
            return ans;
        }

        int[] fact= new int[MAXN];
        int[] inv= new int[MAXN];

        public int Ckn(int n, int k){
            if(k<0 || n<0) return 0;
            if(n<k) return 0;
            return mul(mul(fact[n],inv[k]),inv[n-k]);
        }

        public int inverse(int a){
            return power(a,MOD-2);
        }

        public void preprocess() {
            fact[0]=1;
            for(int i=1;i<MAXN;i++) fact[i]= mul(fact[i-1],i);
            inv[MAXN-1]= inverse(fact[MAXN-1]);
            for(int i=MAXN-2;i>=0;i--){
                inv[i]= mul(inv[i+1],i+1);
            }
        }

        /**
         * return VALUE of lower bound for unsorted array
         */
        public int lowerBoundNormalArray(int[] arr, int x){
            TreeSet<Integer> set= new TreeSet<>();
            for(int num: arr) set.add(num);
            return set.lower(x);
        }
        /**
         * return VALUE of upper bound for unsorted array
         */
        public int upperBoundNormalArray(int[] arr, int x){
            TreeSet<Integer> set= new TreeSet<>();
            for(int num: arr) set.add(num);
            return set.higher(x);
        }

        public void debugArr(int[] arr){
            for(int i: arr) out.print(i+" ");
            out.println();
        }

        public int rand(){
            int min=0, max= MAXN;
            int random_int = (int)Math.floor(Math.random()*(max-min+1)+min);
            return random_int;
        }
        
        public void suffleSort(int[] arr){
            shuffleArray(arr);
            Arrays.sort(arr);
        }


        public void shuffleArray(int[] ar)
        {
            // If running on Java 6 or older, use `new Random()` on RHS here
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
            }
        }
        
        InputReader in; PrintWriter out;
        Scanner sc= new Scanner(System.in);
        CustomFileReader cin;
        int[] xor= new int[3*100000+5];
        int[] pow2= new int[1000000+1];
        public void solve(InputReader in, PrintWriter out) {
            this.in=in; this.out=out;
            // sieve();
            // pow2[0]=1;
            // for(int i=1;i<pow2.length;i++){
            //     pow2[i]= mul(pow2[i-1],2);
            // }
            int t=in.nextInt();
            preprocess();
            // int t=in.nextInt();
            // int t= cin.nextIntArrLine()[0];
            for(int i=1;i<=t;i++) solveC(i);
        }
    
        final double pi= Math.acos(-1);
        static Point base;

        void solveF(int t){
            long a= in.nextLong(), b= in.nextLong();
            String s1= decode(a), s2= decode(b);
            String num="";
            int i=0;
            while(i<s1.length()){
                if(s1.charAt(i)!='0') break;
                i++; 
            }
            int j= s1.length()-1;
            while(j>=0){
                if(s1.charAt(j)!='0') break;
                j--;
            }
            s1= s1.substring(i,j+1);
            String reverse= (new StringBuilder(s1).reverse()).toString();
            if(s2.indexOf(reverse)!=-1) out.println("YES");
            else out.println("NO");

        }

        String decode(long a){
            String s= "";
            while(a>0){
                s+= a%2;
                a/=2;
            }
            return s;

        }
        void solveA(int test) {
            char[] s= in.nextToken().toCharArray();
            String t= in.nextToken();
            int cntA = 0, cntB = 0, cntC = 0;
            for (int i=0; i<s.length; i++) {
                if (s[i] == 'a') cntA++;
                else if (s[i] == 'b') cntB++;
                else if (s[i] == 'c') cntC++;
            }

            Arrays.sort(s);
            if (!t.equals("abc") || cntA == 0 || cntB == 0 || cntC == 0 || s.length < t.length()) {
                out.println(s);
                return;
            }


            int firstB = 0, firstC = 0, lastC = s.length - 1;
            while (firstB < s.length && s[firstB] != 'b') firstB++;
            while (lastC >= 0 && s[lastC] != 'c') lastC--;

            for (int i=0; i<s.length; i++) {
                if (firstB <= i && i <= lastC) {
                    if (cntC!=0) {
                        out.print("c");
                        cntC--;
                    } else if (cntB!=0) {
                        out.print("b");
                        cntB--;
                    }
                }
                else out.print(s[i]);
            }
            out.println();
        }
        
        void solveB(int t) {
            int n= in.nextInt();
            if (n %2 == 0){
                out.println( (n-1) / 2 + " " + (n - 1 - (n - 1)/ 2)  + " " + 1);
                return;
            }
            int u = (n - 1) / 2 + 1, v = n - 1 - u;
            if (_gcd(u,v)==1){
                out.println( u + " " + v + "  " + 1);
                return;
            }
            u++; v--;
            if (_gcd(u,v)==1){
                out.println(u+" "+v+" "+1);
                return;
            }
            assert(false);
            return ;
        }
        
        // int gcd(int a, int b) {
        //     if (b == 0)
        //         return a;
        //     return gcd(b, a % b);
             
        // }
        
        long help(long[] a, long n, int start) {
            long res = a[start];
            if (start == 1) {
                res = a[1];
                for (int i=1; i<=n; i+=2) res = _gcd(res, a[i]);
                if (res == 1) return 0;
                for (int i=2; i<=n; i+=2) if (a[i] % res == 0) return 0;
            }
            else {
                res = a[2];
                for (int i=2; i<=n; i+=2) res = _gcd(res, a[i]);
                if (res == 1) return 0;
                for (int i=1; i<=n; i+=2) if (a[i] % res == 0) return 0;
            }
            return res;
        }
        void solveC(int t) {
            int n= in.nextInt();
            int[] a= new int[n+1];
            boolean[] vis= new boolean[n+1];
            List<Integer> b= new ArrayList<>();
            for (int i=1;i<=n;i++){
                a[i]= in.nextInt();
                if (a[i] <= n && !vis[a[i]]){
                    vis[a[i]]=true;
                }
                else{
                    b.add(a[i]);
                }
            }
            Collections.sort(b);
            int p = (int)b.size()-1;
            for (int i = n; i >= 1; i--){
                if (vis[i]){
                    continue;
                }
                if (b.get(p) <= 2 * i){
                    out.println(-1); return;
                }
                p--;
            }
            out.println(b.size());
        }
        
        void solveD(int t) {
            int n= sc.nextInt();
            int[] res= new int[n+1];
            int zero=-1, one=-1;
            for(int k=1;k<=n;k+=3){
                int ans= query(k,k+1,k+2);
                if(zero==-1 && ans==0) zero= k;
                if(one==-1 && ans==1) one= k;
                if(zero!=-1 && one!=-1) break;
            }
            int zero1= zero, zero2= zero+1, one1= one, one2= one+1;
            if(query(zero1,zero2, one1)==1 || query(zero1,zero2, one2)==1){
                // haha
            }
            else if(query(one1, one2, zero1)==0 || query(one1, one2, zero2)==0) {
                zero1= one1; zero2= one2;
            }
            else{
                zero2= one1;
            }
            int a=-1, b =-1;
            for(int i=1;i<=n;i++){
                if(i!= zero1 && i!=zero2){
                    res[i]= query(zero1, zero2,i);
                    if(a==-1 && res[i]==0) a= i;
                    if(b==-1 && res[i]==1) b=i;
                }
            }
            res[zero1]= query(a,b,zero1);
            res[zero2]= query(a,b,zero2);
            String ans="! ";
            List<Integer> idx= new ArrayList<>();
            for(int i=1;i<=n;i++){
                if(res[i]==0) idx.add(i);
            }
            
            if(idx.size()>0){
                ans+= idx.size()+" ";
                for(int i: idx) ans+= i+" ";
            }
            ans= ans.trim();
            System.out.println(ans);
            System.out.flush();
        }
        
        int query(int a, int b, int c){
            System.out.println("? "+a+" "+b+" "+c);
            System.out.flush();
            int ans= sc.nextInt();
            return ans;
        }

        



        static class Node implements Comparable<Node>{
            char op;
            int s;
            public Node (char op, int s) {
                this.op= op;
                this.s= s;
            }
            @Override
            public int compareTo(Node o) {
                if (this.s==o.s) return (int)(this.op-o.op);
                return this.s-o.s;
            }

        }

        private long distance(Point p1, Point p2) {
            long x= p1.x-p2.x, y= p1.y-p2.y;
            return x*x+y*y;
        }


        private boolean eqPoint(Point p1, Point p2){
            return p1.x==p2.x && p1.y==p2.y;
        }

        private double polarAngle(Point p1, Point p2) {
            // p1 -> p2
            if (p1.x==p2.x) return pi/2;
            else if (p1.y==p2.y){
                if(p1.x<p2.x) return 0;
                else return pi;
            }
            else {
                double y= (double)p2.y-(double)p1.y;
                double x= (double)p2.x-(double)p1.x;
                BigDecimal alpha1= new BigDecimal(y);
                BigDecimal alpha2= new BigDecimal(x);
                BigDecimal val= alpha1.divide(alpha2);

                double angle= Math.atan(val.doubleValue());
                if (angle<0) angle+= pi;
                out.println("angle: "+angle);
                return angle;
            }
        }

        private boolean isRightTurn(Point p1, Point p2, Point p3){
            Vector v1= new Vector(p1,p2), v2= new Vector(p1,p3);
            if(crossProd(v1,v2)<0) return true;
            else return false;
        }

        private long crossProd(Vector v1, Vector v2){
            //x1*y2-x2*y1
            return v1.x*v2.y - v2.x*v1.y;
        }

        static class PointAngle implements Comparable<PointAngle>{
            Point p;
            double angle;
            long dis;
            public PointAngle(Point p, double angle, long dis) {
                this.p= p;
                this.angle= angle;
                this.dis= dis;

            }

            @Override
            public int compareTo(PointAngle o) {
                double dif= this.angle-o.angle;
                if (dif <0) return -1;
                else if(dif >0) return 1;
                else {
                    long dif2r= this.dis-o.dis;
                    long dif2l= o.dis-this.dis;

                    if (base.x < this.p.x) return intDif(dif2r);
                    else return intDif(dif2l); 
                    
                }
            }

            private int intDif(long a){
                if (a>0) return 1;
                else if(a<0) return -1;
                else return 0;
            }
        }


    
        
        public long _gcd(long a,  long b)
        {

            if(b == 0) {
                return a;
            }
            else {
                return _gcd(b, a % b);
            }
        }
        public long _lcm(long a, long b){
            return (a*b)/_gcd(a,b);
        }

    }


    // static class SEG {

    //     Pair[] segtree;
        
    //     public SEG(int n){
            
    //         segtree= new Pair[4*n];
    //         Arrays.fill(segtree, new Pair(-1,Long.MAX_VALUE));
    //     }
    //     // void buildTree(int l, int r, int index) {
    //     //     if (l == r) {
    //     //         segtree[index].y = a[l];
    //     //         return;
    //     //     }
    //     //     int mid = (l + r) / 2;
    //     //     buildTree(l, mid, 2 * index + 1);
    //     //     buildTree(mid + 1, r, 2 * index + 2);
    //     //     segtree[index].y = Math.min(segtree[2 * index + 1].y, segtree[2 * index + 2].y);
    //     // }
        
    //     void update(int l, int r, int index, int pos, Pair val) {
    //         if (l == r) {
    //             segtree[index] = val;
    //             return;
    //         }
    //         int mid = (l + r) / 2;
    //         if (pos <= mid) update(l, mid, 2 * index + 1, pos, val);
    //         else update(mid + 1, r, 2 * index + 2, pos, val);
    //         if(segtree[2 * index + 1].y < segtree[2 * index + 2].y){
    //             segtree[index]= segtree[2 * index + 1];
    //         }
    //         else {
    //             segtree[index]= segtree[2 * index + 2];
    //         }
    //     }
        
    //     // Pair query(int l, int r, int from, int to, int index) {
    //     //     if (from <= l && r <= to)
    //     //         return segtree[index];
    //     //     if (r < from | to < l)
    //     //         return 0;
    //     //     int mid = (l + r) / 2;
    //     //     Pair left= query(l, mid, from, to, 2 * index + 1);
    //     //     Pair right= query(mid + 1, r, from, to, 2 * index + 2);
    //     //     if(left.y < right.y) return left;
    //     //     else return right;
            
    //     // }
        
        
    // }

    static class Venice{
        public Map<Long,Long> m= new HashMap<>();
        public long base=0;
        public long totalValue=0;
        private int M= 1000000007;

        private long addMod(long a, long b){
            a+=b;
            if(a>=M) a-=M;
            return a;
        }

        public void reset(){
            m= new HashMap<>();
            base=0;
            totalValue=0;
        }
        public void update(long add){
            base= base+ add;
        }
        public void add(long key, long val){
            long newKey= key-base;
            m.put(newKey, addMod(m.getOrDefault(newKey,(long)0),val));
        }
    }



    static class Tuple implements Comparable<Tuple>{
        int x, y, z;
        public Tuple(int x, int y, int z){
            this.x= x;
            this.y= y;
            this.z=z;
        }
        @Override
        public int compareTo(Tuple o){
            return this.z-o.z;
        }
    }

    static class Point implements Comparable<Point>{
        public long x;
        public long y;
        public Point(long x, long y){
            this.x= x;
            this.y= y;
        }

        @Override
        public int compareTo(Point o) {
            if(this.y!=o.y) return (int)(this.y-o.y);
            return (int)(this.x-o.x);
        }
    }

    static class Vector {
        public long x;
        public long y;

        // p1 -> p2
        public Vector(Point p1, Point p2){
            this.x= p2.x-p1.x;
            this.y= p2.y-p1.y;
        }
    }

    static class Pair implements Comparable<Pair>{
        public int x;
        public int y;
        public Pair(int x, int y){
            this.x= x;
            this.y= y;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.x!=o.x) return this.x-o.x;
            return (int)(this.y-o.y);
        }
    }

    // public static class compareL implements Comparator<Tuple>{
    //     @Override
    //     public int compare(Tuple t1, Tuple t2) {
    //         return t2.l - t1.l;
    //     }
    // }

    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public double nextDouble(){
            return Double.parseDouble(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
        public int[] nextIntArr(int n){
            int[] arr= new int[n];
            for(int i=0;i<n;i++) arr[i]= nextInt();
            return arr;
        }
        public long[] nextLongArr(int n){
            long[] arr= new long[n];
            for(int i=0;i<n;i++) arr[i]= nextLong();
            return arr;
        }
        public List<Integer> nextIntList(int n){
            List<Integer> arr= new ArrayList<>();
            for(int i=0;i<n;i++) arr.add(nextInt());
            return arr;
        }
        public int[][] nextIntMatArr(int n, int m){
            int[][] mat= new int[n][m];
            for(int i=0;i<n;i++) for(int j=0;j<m;j++) mat[i][j]= nextInt();
            return mat;
        }
        public List<List<Integer>> nextIntMatList(int n, int m){
            List<List<Integer>> mat= new ArrayList<>();
            for(int i=0;i<n;i++){
                List<Integer> temp= new ArrayList<>();
                for(int j=0;j<m;j++) temp.add(nextInt());
                mat.add(temp);
            }
            return mat;
        }
        public char[] nextStringCharArr(){
            return nextToken().toCharArray();
        }
    }

    static class CustomFileReader{
        String path="";
        Scanner sc;
        public CustomFileReader(String path){
            this.path=path;
            try{
                sc= new Scanner(new File(path));
            }
            catch(Exception e){}
        }
        public String nextLine(){
            return sc.nextLine();
        }
        public int[] nextIntArrLine(){
            String line= sc.nextLine();
            String[] part= line.split("[\\s+]");
            int[] res= new int[part.length];
            for(int i=0;i<res.length;i++) res[i]= Integer.parseInt(part[i]);
            return res;
        }
    }
}