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 collections
# import random
# import math
# import itertools
# import math
# mport math
import bisect
# from collections import defaultdict
# import itertools
# from sys import stdin, stdout
# import math
# import math
# import bisect
# import bisect
# import collections
# import itertools
# import math
import collections
import itertools
import math
import sys

# import operator
# from decimal import Decimal

# sys.setrecursionlimit(10**6)





p2D = lambda x: print(*x, sep="\n")


def II(): return int(sys.stdin.buffer.readline())


def MI(): return map(int, sys.stdin.buffer.readline().split())


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def BI(): return sys.stdin.buffer.readline().rstrip()


def SI(): return sys.stdin.buffer.readline().rstrip().decode()


def li(): return [int(i) for i in input().split()]


def lli(rows): return [li() for _ in range(rows)]


def si(): return input()


def ii(): return int(input())


def ins(): return input().split()


# mod = 10**9+7
# fval = [1]
# for i in range(1,200001):
#     x = (fval[-1]*i)%mod
#     fval.append(x)
#
# ifac = [1]*(200001)
# ifac[200000] = pow(fval[200000], -1, mod)
# for i in range(200000-1, 1, -1): ifac[i] = ifac[i+1]*(i+1)%mod
# _________________ For taking Input from the Text Files __________________
# import os.path
#
# if (os.path.exists('input.txt')):
#     sys.stdin = open("input.txt", "r")
#     sys.stdout = open("output.txt", "w")
#     sys.stderr = open("error.txt", "w")

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1



def binary_search(n, a):
    l = len(a)
    low = 0
    high = l-1
    while high>=low:
        mid = (high+low)//2
        if a[mid] == n:
            return mid
        elif a[mid]>n:
            high = mid-1
        else:
            low = mid+1
    return -1

is_prime = [True]*(10**6+1)
def primeseive(n):
    is_prime[0] = is_prime[1] = False
    i = 2
    while i*i<=n:
        if is_prime[i] == True:
            for j in range(i*i,n+1,i):
                is_prime[j] = False
        i+=1


def solve():


    #third problem
    #
    n = II()
    a = LI()
    a.sort()
    x = 0
    ma = [0]*n
    pa = []
    for i in range(n):
        if a[i]<n+1 and ma[a[i]-1]==0:
            ma[a[i]-1] = 1
        else:pa.append(a[i])
    p = [i+1 for i in range(n) if ma[i]==0]
    pa.sort()
    for i in range(len(pa)):
        if pa[i]>= 2*p[i]+1:
            x+=1
            continue
        return -1
    return x

    #fourth problem
    # n = ii()
    # #patterns = 123, 124, 234, 134
    # fp = [0]*2
    # sp = [0]*2
    # tp = [0]*2
    # fop = [0]*2
    # fp[0]= ['0000', '0010', '0100', '1000', '0001', '0011', '0101', '1001' ]
    # fp[1] = ['1111', '1101', '1011', '0111', '1110', '1100', '1010', '0110']
    # sp[0] = ['0000', '0010', '0100', '0110', '0001', '0011', '1000', '1010']
    # sp[1] = ['1111', '1101', '1011', '1001', '1110', '1100', '0111', '0101']
    # tp[0] = ['0000', '1000', '0100', '1100', '0010', '1010', '0001', '1001']
    # tp[1] = ['1111', '0111', '1011', '0011', '1101', '0101', '1110', '0110']
    # fop[0] = ['0000', '0100', '1000', '1100', '0010', '0110', '0001', '0101']
    # fop[1] = ['1111', '1011', '0111', '0011', '1101', '1001', '1110', '1010']
    # x = n%4
    # ans = ''
    # for k in range(1,n//4+1):
    #     i = 4*k
    #     print("? {} {} {}".format(i, i+1, i+2), flush=True)
    #     m = fp[int(input())]
    #     print("? {} {} {}".format(i, i + 1, i + 3), flush=True)
    #     n = sp[int(input())]
    #     print("? {} {} {}".format(i+1, i + 2, i + 3), flush=True)
    #     o = tp[int(input())]
    #     print("? {} {} {}".format(i, i + 2, i + 3), flush=True)
    #     p = fop[int(input())]
    #     ans += (((set(m) and set(n)) and set(o)) and set(p))
    # u=v=w=z=-1
    # if '11' in ans:
    #     u = ans.find('11')
    # elif '00' in ans:
    #     v = ans.find('00')
    # elif '01' in ans:
    #     w = ans.find('01')
    # else:
    #     z = ans.find('10')
    # for j in range(x):
    #     if u!=-1:
    #         print("? {} {} {}".format(u+1, u+2, i+j+5), flush=True)
    #         m = fp[int(input())]
    #         if
    #     elif v!=-1:
    #
    #     elif w!=-1:
    #
    #     else:

def main():
    #primeseive(10**6)
    #print(is_prime)
    for _ in range(II()):
    #print(solve())
        sys.stdout.write(str(solve()) + "\n")
    # print(solve())

    #     z += str(ans) + '\n'
    # print(len(ans), ' '.join(map(str, ans)), sep='\n')
    # stdout.write(z)


# for interactive problems
# print("? {} {}".format(l,m), flush=True)
# or print this after each print statement
# sys.stdout.flush()


if __name__ == "__main__":
    main()