玛丽亚是家里最活跃的老太太。她厌倦了坐在家里。她决定组织一场抗击冠状病毒的仪式。
她有 $$$n$$$ 个朋友,他们也是奶奶(玛丽亚不包括在这个数字中)。第 $$$i$$$ 奶奶已经准备好参加仪式,前提是当她出现在院子里时,那里至少有 $$$a_i$$$ 的其他奶奶。请注意,奶奶可以同时进入庭院。正式来说,如果先来的或与她同时到来的其他奶奶的数量大于或等于 $$$a_i$$$,则奶奶 $$$i$$$ 同意来。
老奶奶们就这样聚集在院子里。
- 最初,院子里只有玛丽亚(也就是说,院子里的奶奶最初数量为$$$1$$$)。所有剩下的$$$n$$$奶奶仍然坐在家里。
- 在每一步中,玛丽亚都会选择一组奶奶,其中没有一个人尚未进入庭院。她向他们每个人保证,当她出现时,院子里至少会有$$$a_i$$$其他奶奶(包括玛丽亚)。玛丽亚可以同时给几个奶奶打电话。在这种情况下,被选中的奶奶会在同一时间到院子里去。
- 她不能欺骗奶奶,即第$$$i$$$个奶奶在出现在庭院的那一刻,发现现在严格少于$$$a_i$$$的其他奶奶(除了她自己,但包括玛丽亚)的情况,是禁止的。请注意,如果几个奶奶同时出现在院子里,那么每个奶奶在出现时都会看到其他奶奶。
你的任务是找出玛丽亚可以在院子里收集最多数量的奶奶(包括她自己)参加仪式。毕竟,隔离期间聚集在一个地方的人越多,仪式就越有效!
考虑一个例子:如果 $$$n=6$$$ 且 $$$a=[1,5,4,5,1,9]$$$,则:
- 第一步,玛丽亚可以用号码 $$$1$$$ 和 $$$5$$$ 呼叫奶奶,他们每个人在走出院子的那一刻都会看到两个奶奶(注意 $$$a_1=1 \le 2$$$ 和 $$$a_5=1 \le 2$$$);
- 第二步,玛丽亚可以用号码 $$$2$$$、$$$3$$$ 和 $$$4$$$ 呼叫老奶奶,他们每个人在出去到院子的那一刻都会看到五个老奶奶(注意 $$$a_2=5 \le 5$$$、$$$a_3=4 \le 5$$$ 和 $$$a_4=5 \le 5$$$);
- 第 $$$6$$$ 个奶奶不能被叫到院子里 - 因此,答案是 $$$6$$$(玛丽亚本人和另一个 $$$5$$$ 奶奶)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 奶奶的数量(玛丽亚不包括在这个数字中)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$)。
保证输入的所有测试用例的值 $$$n$$$ 之和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$k$$$ ($$$1 \le k \le n + 1$$$) — 院子里奶奶的最大可能数量。
示例
输入 #1
4 5 1 1 2 2 1 6 2 3 4 5 6 7 6 1 5 4 5 1 9 5 1 2 3 5 6
输出 #1
6 1 6 4
注意
在示例中的第一个测试用例中,第一步 Maria 可以呼叫所有奶奶。然后他们每人出来都会看到五个奶奶。因此,玛丽亚和其他五个奶奶会在院子里。
在示例中的第二个测试用例中,没有人可以在院子里,因此玛丽亚将独自留在那儿。
上面详细描述了示例中的第三个测试用例。
在示例的第四个测试用例中,在第一步,Maria 可以呼叫编号为 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的奶奶。如果在第二步玛丽亚叫$$$4$$$或$$$5$$$(其中之一),那么当一位奶奶出现在院子里时,她只会看到四个奶奶(但这是被禁止的)。这意味着 Maria 无法分别呼叫第 $$$4$$$ 奶奶或第 $$$5$$$ 奶奶(其中之一)。如果她同时拨打:$$$4$$$ 和 $$$5$$$,那么当他们出现时,他们会看到 $$$4+1=5$$$ 老奶奶。尽管对于第 $$$4$$$ 的奶奶来说已经足够了,但第 $$$5$$$ 的奶奶却不满意。因此,Maria 不能同时给第 $$$4$$$ 奶奶和第 $$$5$$$ 奶奶打电话。也就是说,玛丽亚和第一步的三个奶奶总共会在院子里。