A. Tree Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of $$$n$$$ positive integers.

Each integer represents the maximum number of connections a node can have.

You have to partition the sequence into the minimum possible number of non-empty subsequences.

Each element must belong to exactly one subsequence.

A subsequence is called valid if its elements can form a connected rooted tree such that:

  • the first element of the subsequence is the root;
  • every child appears after its parent in the subsequence;
  • for every node, the number of edges connected to it does not exceed its value.

Your task is to find the minimum number of valid subsequences needed to partition the given sequence.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the maximum number of connections each node can have.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of valid subsequences needed to partition the given sequence.

Example
Input
3
3
2 1 1
2
1 1
6
2 1 3 1 1 2
Output
1
1
2
Note