codeforces#P1826A. Trust Nobody

    ID: 33790 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcegreedyimplementationsortings

Trust Nobody

Description

There is a group of nn people. Some of them might be liars, who always tell lies. Other people always tell the truth. The ii-th person says "There are at least lil_i liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.

The first line contains a single integer tt (1t10001 \leq t \leq 1000) — the number of test cases.

The first line of each test case contains a single integer nn (1n1001 \leq n \leq 100).

The second line of each test case contains nn integers lil_i (0lin0 \leq l_i \leq n) — the number said by the ii-th person.

It's guaranteed that the sum of all nn does not exceed 10410^4.

For each test case output a single integer. If what people are saying is contradictory, output 1-1. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

Input

The first line contains a single integer tt (1t10001 \leq t \leq 1000) — the number of test cases.

The first line of each test case contains a single integer nn (1n1001 \leq n \leq 100).

The second line of each test case contains nn integers lil_i (0lin0 \leq l_i \leq n) — the number said by the ii-th person.

It's guaranteed that the sum of all nn does not exceed 10410^4.

Output

For each test case output a single integer. If what people are saying is contradictory, output 1-1. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

输入数据 1

7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5

输出数据 1

1
-1
0
-1
0
3
4

Note

In the first example, the only possible answer is that the second person is a liar, so the answer is 11 liar.

In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.

In the third example, everybody tells the truth, so the answer is 00 liars.