题目描述

题目背景

地灵殿深处，并非总是灼热与哀嚎。在一间有着高大古旧书架、光线昏黄而温暖的房间里，古明地觉正端坐在一张宽大的椅子上。她手中捧着一本从地上世界传来的、画风稚拙可爱的绘本，封面上画着笑容夸张的太阳和手拉手的小动物。

她读得很慢，很仔细。并非不认识文字，而是她在努力地“感受”。通过指尖触碰书页，通过眼睛凝视图画，她试图去理解画面中那种名为“快乐”的、明亮鲜艳的色彩背后，究竟是怎样一种情感的“波长”。她空洞的、裸露在外的第三只眼（恋恋的心眼）微微流转着光芒，无声地解析着这一切。

妹妹古明地恋，则像一只慵懒的猫，整个身体趴在她姐姐的膝头。恋恋紧闭着“读心”之眼，让自己处于无意识漫步的状态，按理说无法直接感知任何具体思维。但此刻，她却仿佛能感受到一种温暖的、平稳的、如同深海暗流般缓缓流淌的“波段”从姐姐身上传来。这波段不携带具体信息，只是一种安心的“氛围”。她舒服地蹭了蹭，发出细微的、满足的咕噜声。

火焰猫燐阿燐蜷在房间角落的软垫上，尾巴尖有一下没一下地轻轻拍打着地面。她偶尔抬起眼皮，看看安静读书的觉大人和像小动物一样依偎着的恋大人，然后又会惬意地眯上眼。地狱鸦灵乌路空阿空可能正在熔岩河里游泳，也可能在某个地方晒太阳，但此刻都不重要。这个昏暗的房间，被书页翻动的沙沙声、平稳的呼吸声和一种无声的温情所填满，是灼热地狱中一个珍贵的、静谧的避风港。

题目描述

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

其中，重排是指将原数组 \(a_1, a_2, \cdots, 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\)。