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

from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
#from collections import deque, Counter, OrderedDict, defaultdict
#import heapq
#ceil,floor,log,sqrt,factorial,pow,pi,gcd
#import bisect
#from bisect import bisect_left,bisect_right

BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b"\n") + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode("ascii"))
		self.read = lambda: self.buffer.read().decode("ascii")
		self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
	"""Prints the values to a stream, or to sys.stdout by default."""
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()


if sys.version_info[0] < 3:
	sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
	sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return(int(input()))
def lint():
    return(list(map(int,input().split())))
def insr():
    s = input().strip()
    return(list(s[:len(s)]))
def invr():
    return(map(int,input().split()))
import itertools
from sys import maxsize, stdout, stdin,stderr
# mod = int(1e9+7)
import sys
# def I(): return int(stdin.readline())
# def lint(): return [int(x) for x in stdin.readline().split()]
def S(): return list(map(str,input().strip()))
def grid(r, c): return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop , heappush
import bisect
from math import factorial, inf
from itertools import groupby
from itertools import permutations as comb

# mod=1000000007
mod = 998244353
def gcd(a,b): 
    while b:
        a %= b
        tmp = a
        a = b
        b = tmp
    
    return a
 
def lcm(a,b): 
    return a  // gcd(a, b) * b
 
def check_prime(n):
    for i in range(2, int(n ** (1 / 2)) + 1):
        if not n % i:
            return False
    return True

# def nCr(n, r):
 
#     return (fact(n) // (fact(r)
#                 * fact(n - r)))
 
# Returns factorial of n
# def fact(n):
 
#     res = 1
     
#     for i in range(2, n+1):
#         res = res * i
         
#     return res
def primefactors(n):
    num=0
    
    while n % 2 == 0:
        num+=1
        n = n / 2
    
    for i in range(3,int(math.sqrt(n))+1,2):
         
    
        while n % i== 0:
            num+=1
            n = n // i
               
    
    if n > 2:
        num+=1
    return num
'''
def iter_ds(src):
    store=[src]
    while len(store):
        tmp=store.pop()
        if not vis[tmp]:
            vis[tmp]=True
            for j in ar[tmp]:
                store.append(j)
'''
def ask(a,b,c):
    # print('? 1 {}'.format(a),flush=True)
    print(c,a,b,flush=True)
    n=I()
    
    return n
def linear_sieve(n):
    is_composite=[False]*n
    prime=[]
    for i in range(2,n):
        if not is_composite[i]:
            prime.append(i)
        for j in prime:
            is_composite[i*j]=True
            if i%prime==0:
                break
    return prime
 
def dfs(i,p,d):
    
    a,tmp=0,0
    for j in d[i]:
        if j!=p:
            a+=1
            tmp+=dfs(j,i)
    
    if a==0:
        return 0
    
    return tmp/a + 1 
def primeFactors(n):
    l=[]
    
    while n % 2 == 0:
        l.append(2)
        n = n // 2
    for i in range(3,int(math.sqrt(n))+1,2):
         
        
        while n % i== 0:
            l.append(i)
            n = n // i

    if n > 2:
        l.append(n)
    return l

def binpow(a,b,c):
    res=1
    a=a%c
    while b>0:
        if b&1:
            res=(res*a)%c

        b=b>>1
        a = (a*a)%c

    return res-1


    

#  Sieve
d=[]
primes=[]
prim=[0]*(10**6+1)
def sieve(n):
    
    for i in range(n):
        d.append(i)

    for i in range(2,n):

        if d[i]==i:
            prim[i]=1
            primes.append(i)
        j=0
        while j<len(primes) and primes[j]<=d[i] and primes[j]*i<n:
        
            d[i * primes[j]] = primes[j]
            j+=1

        
def primeFactors(n):
    factors=[]
    while n!=1:
        factors.append(d[n])
        n//=d[n]
    
    return factors

t = 1
t = I()

for _ in range(t):
    n=I()
    s = lint()
    s.sort()
    cnt=0
    b=defaultdict(lambda:0)
    c=[0]*n
    for i in range(n):
        if s[i]<n+1 and b[s[i]]==0:
            c[i]=1
            b[s[i]]=1
    l=[]
    m=[]
    for i in range(n):
        if c[i]==0:
            l.append(s[i])
    for i in range(1,n+1):
        if b[i]==0:
            m.append(i)
    
    for i in range(len(l)):
        b=l[i]-(m[i])
        if l[i]==m[i]:
            continue
        elif(l[i]%b!=m[i] or b<=0):
            cnt=-1
            break
        else:
            cnt+=1
    print(cnt)

    

        


    