D. Matryoshkas
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Matryoshkas are traditional Russian wooden dolls that nest inside one another. Mathias has found a box full of them and wants to put together an exhibition!

The box contains $$$n$$$ separate dolls. Doll $$$j$$$ has size $$$a_j$$$, an integer between $$$1$$$ and $$$n$$$. Several dolls may have the same size.

To assemble a set of size $$$i$$$, Mathias must choose exactly one doll of each size $$$1,2,\ldots,i$$$ and nest them from smallest to largest. Such a set uses $$$i$$$ dolls, and its outermost doll has size $$$i$$$. A single doll of size $$$1$$$ also forms a valid set.

To make the exhibition varied, Mathias wants all the sets to have distinct sizes. Each doll may belong to at most one set, and he does not have to use every doll in the box.

What is the largest number of sets he can assemble?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^{5}$$$), the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$), the number of dolls. The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_j \leq n$$$), their sizes.

The sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.

Output

For each test case, print a single integer on a separate line: the maximum number of sets of distinct sizes that can be assembled.

Example
Input
5
1
1
4
1 2 3 1
3
2 3 2
4
1 1 1 1
6
3 1 2 1 2 1
Output
1
2
0
1
3
Note

In the second test case, sets of sizes $$$1$$$ and $$$2$$$ can be assembled, leaving the doll of size $$$3$$$ unused. In the fourth test case, only one set of size $$$1$$$ can be assembled, since all set sizes must be distinct. In the fifth test case, sets of sizes $$$1$$$, $$$2$$$, and $$$3$$$ use all the dolls.