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

# cook your dish here
import sys
#import random
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
#sys.setrecursionlimit(10**8)
from queue import PriorityQueue as pq
from math import gcd
#import math
input_ = lambda: sys.stdin.readline().strip("\r\n")
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab,bc,cd : ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x : print(x)
prinT = lambda x : print(x)
f = lambda : sys.stdout.flush()
inv =lambda x:pow(x,mod-2,mod)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
mod = 10**9 + 7
mod1 = 998244353


for _ in range (ii()) :
    n = ii()
    a = il()

    a.sort()

    b = [0 for i in range (n+1)]

    c = []

    for i in range (n) :
        if (a[i] <= n) :
            b[a[i]] += 1

    for i in range (1,1+n) :
        if (b[i] == 0) :
            c.append(i)

    ans = len(c)

    for i in range (n-1,-1,-1) :
        if (len(c) == 0) :
            break

        fl = 1

        if (a[i] <= n and b[a[i]] == 1) :
            fl = 0

        if (fl and a[i]>2*c[-1] and c[-1] != 1) :
            if (a[i] <= n) :
                b[a[i]] -= 1

            a[i] = c[-1]
            b[c[-1]] += 1
            c.pop()

        if (len(c) > 0 and c[-1] == 1) :
            ind = 0

            for i in range (n) :
                if (a[i] > n) :
                    ind = a[i]
                    break
                elif (b[a[i]] > 1) :
                    ind = a[i]
                    break

            if (ind != 2) :
                c.pop()


    if (len(c) == 0) :
        print(ans)
    else :
        print(-1)

        

    
    
