一个由 $$$n$$$ 人组成的公司正计划去电影院。每个人要么去看电影,要么不去看电影。这取决于还有多少人会去。具体来说,每个人 $$$i$$$ 都说:“当且仅当至少 $$$a_i$$$ 其他人会去时,我想去电影院,不包括我自己”。这意味着如果出现以下情况,$$$i$$$ 就会变得悲伤:
- 他们去电影院,并且严格少于其他人去的$$$a_i$$$;或
- 他们不去电影院,至少 $$$a_i$$$ 其他人去了。
有多少种方法可以选择一组去看电影的人,以便没有人感到悲伤?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 公司的人数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) - 来自人们声明的整数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 选择一组人去看电影的不同方式的数量,这样就不会有人感到悲伤。
示例
输入 #1
4 2 1 1 7 0 1 2 3 4 5 6 8 6 0 3 3 6 7 2 7 5 3 0 0 3 3
输出 #1
2 1 3 2
注意
在第一个测试用例中,当且仅当另一个人去时,两个人都想去电影院。有两个有效的选择:要么两个人都去,要么两个人都不去。但如果其中一个人走了,两人都会伤心。
在第二个测试用例中,每个人都必须去电影院。不然的话,就会有人伤心。
在第三个测试用例中,有三个有效选项:编号$$$2$$$的人去电影院;或索引为 $$$2, 3, 4, 7$$$ 的人去;或者八个人都去。