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

# Problem: C. Паприка и перестановка
# Contest: Codeforces - Codeforces Round #761 (Div. 2)
# URL: https://codeforces.com/contest/1617/problem/C
# Memory Limit: 256 MB
# Time Limit: 1000 ms
# 
# Powered by CP Editor (https://cpeditor.org)

import bisect

mod = 10 ** 9 + 7
eps = 10 ** -9


def __gcd(a, b):
	return a if b == 0 else __gcd(b, a % b)
	

def __lcm(a, b):
	return a * b / __gcd(a, b)


def __fact(n):
	return 1 if n == 1 else n * __fact(n - 1)


def __mex(a):
	mex = 0
	a.sort()
	for x in a:
		if x <= mex:
			mex += 1
		else:
			break
	return mex

def __dist(x1, y1, x2, y2):
	return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
     
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __modInverse(a, m):
    
    m0 = m
    y = 0
    x = 1
    if (m == 1):
        return 0
    
    while(a > 1):
    	q = a // m
    	t = m
    	m = a % m
    	a = t
    	t = y
    	y = x - q * y
    	x = t
    if (x < 0):
    	x = x + m0
    return x
    
    
    
def __isprime(n):
	if n < 2:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
	
def __cntprimediv(n):
	ret = 0
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			n //= i
			ret += 1
		i += 1
	if n > 1:
		ret += 1
	return ret
	
def __primefactors(n):
	ret = []
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret
	

def __sumdigit(n):
	ret = 0
	while n > 0:
		ret += n % 10
		n //= 10
	return ret

def __zfunc(s):
	n = len(s)
	z = [0 for i in range(n)]
	l = 0
	r = 0
	for i in range(1, n):
		if r >= i:
			z[i] = min(z[i - l], r - i + 1)
		while z[i] + i < n and s[z[i]] == s[z[i] + i]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z
	
	
def __to(n, x):
	ret = ''
	while n > 0:
		q = n % x
		if q < 10:
			ret += str(q)
		else:
			ret += chr(q - 10 + ord('a'))
		n //= x
	return ret[::-1]
	
	
def solve(t):

	n = int(input())
	a = list(map(int, input().split()))
	needs = [True for i in range(n + 1)]
	v = []
	vv = []
	for i in range(n):
		if a[i] <= n and needs[a[i]]:
			needs[a[i]] = False 
		else:
			vv.append(a[i])
			v.append(i + 1)
	a.sort()
	cnt = 0
	for i in range(len(v)):
		if v[i] * 2 < vv[i]:
			cnt += 1
		else:
			cnt = -1
			break
	print(cnt)
	
t = 1
t = int(input())


for i in range(t):
	solve(i + 1)