题目描述

给定一个长为 $n$ 的数组 $a_1,a_2⋯,a_n$，求将其重排后满足 $a_i=i$ 的下标 $i$（$1 \le i \le n$）的数量最大值。

其中，重排是指将原数组 $a_1,a_2,⋯,a_n$ 中的元素按照任意顺序重新排列，得到一个新的数组，新数组中的元素与原数组完全相同（包括重复元素），只有顺序不同。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行，包含一个正整数 $n$（$1 \le n \le 5 \times 10^5$)，表示数组的长度为 $n$。

接下来一行，包含 $n$ 个正整数，第 $i$ 个数表示数组中的第 $i$ 个数 $a_i$（$1 \le a_i \le 10^9$）。

保证所有测试数据的 $n$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出一行，一个非负整数，表示重排后数组中满足 $a_i=i$ 的下标 $i$ 的数量的最大值。

样例

2
5
5 3 2 1 3
6
4 2 1 9 8 7

4
3

样例解释

在样例测试用例 1 中，一种可能的重排后的数组是 $[1,2,3,3,5]$，第 $1,2,3,5$ 位满足 $a_i=i$。可以证明此时满足 $a_i=i$ 的下标 $i$ 的数量到达最大值 $4$。

在样例测试用例 2 中，一种可能的重新排列后的数组是 $[1,2,8,4,7,9]$。可以证明此时满足 $a_i=i$ 的下标 $i$ 的数量到达最大值 $3$。