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

# Sujith
from sys import stdin,stdout,setrecursionlimit
from io import BytesIO, IOBase
# from heapq import heappush as push,heappop as hp,heapify as h
# from math import gcd,floor,sqrt,ceil
from collections import Counter,deque as dq,defaultdict as dd
# from itertools import accumulate as acc,permutations as perm
# from bisect import bisect_left as bl,bisect_right as br,bisect as bis

setrecursionlimit(10000)

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        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
        self.BUFSIZE = 8192

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

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

    def flush(self):
        if self.writable:
            self.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")


stdin, stdout = IOWrapper(stdin), IOWrapper(stdout)
input = lambda: stdin.readline().rstrip("\r\n")

# inf = float('inf')
# ninf = float('-inf')
# abc = 'abcdefghijklmnopqrstuvwxyz'
inp = lambda: int(input())
st = lambda: input().strip()
jn = lambda x,l: x.join(map(str,l))
int_arr = lambda : list(map(int,input().strip().split()))
str_arr = lambda :list(map(str,input().split()))
get_str = lambda : map(str,input().strip().split())
get_int = lambda: map(int,input().strip().split())
get_float = lambda : map(float,input().strip().split())

mod = 1000000007

#main()
for _ in range(inp()):
    n = inp()
    arr = int_arr()

    ans = []
    pres,miss = dd(int),[]
    for i in range(n):
        if arr[i] > n:
            if arr[i] % 2 != 0:
                ans.append(arr[i] // 2)
            else:
                ans.append((arr[i] // 2) - 1)
        else:
            pres[arr[i]] = 1
    ind = 0
    tot = 0
    cond = True
    ans.sort()
    l = len(ans)
    for i in range(1,n + 1):
        if not pres[i]:
            if ind < l and ans[ind] >= i:
                tot += 1
                ind += 1
            else:
                cond = False
                break
    if not cond:
        print(-1)
    else:
        print(tot)