给定一个数组 $$$a$$$ 和 $$$n$$$ 整数。按非降序排序,即对所有 $$$1 \le i \lt n$$$ 为 $$$a_i \le a_{i + 1}$$$。
您可以从数组中删除任意数量的元素(包括根本不删除任何元素的选项),而无需更改剩余元素的顺序。删除后,将发生以下情况:
- $$$a_1$$$ 写入新数组;
- 如果 $$$a_1 + 1 \lt a_2$$$,则将 $$$a_2$$$ 写入新数组;否则,$$$a_2$$$ 被写入与 $$$a_1$$$ 相同的数组;
- 如果 $$$a_2 + 1 \lt a_3$$$,则将 $$$a_3$$$ 写入新数组;否则,$$$a_3$$$ 被写入与 $$$a_2$$$ 相同的数组;
- $$$\cdots$$$
例如,如果 $$$a=[1, 2, 4, 6]$$$,则:
- $$$a_1 = 1$$$ 写入新数组,得到数组:$$$[1]$$$;
- $$$a_1 + 1 = 2$$$,因此 $$$a_2 = 2$$$ 被添加到现有数组中,得到数组:$$$[1, 2]$$$;
- $$$a_2 + 1 = 3$$$,因此 $$$a_3 = 4$$$ 被写入新数组,得到数组:$$$[1, 2]$$$ 和 $$$[4]$$$;
- $$$a_3 + 1 = 5$$$,因此 $$$a_4 = 6$$$ 被写入新数组,从而生成数组:$$$[1, 2]$$$、$$$[4]$$$ 和 $$$[6]$$$。
您的任务是以所描述的算法创建尽可能多的数组的方式删除元素。如果从数组中删除所有元素,则不会创建新数组。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$, $$$a_i \le a_{i + 1}$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——通过删除任意(可能为零)数量的元素可以获得的数组的最大数量。
示例
输入复制
661 2 3 4 5 631 2 341 2 2 41231 4 821 1
输出复制
3 2 2 1 3 1
注意
第一个例子中,可以去掉$$$a_3$$$和$$$a_5$$$,则$$$a=[1, 2, 4, 6]$$$,其组建数组的过程如语句所示。
在第二个例子中,需要删除$$$a_2$$$,之后$$$a = [1, 3]$$$,并且将写入数组$$$[1]$$$和$$$[3]$$$。
在第三个示例中,不需要删除;对于 $$$a = [1, 2, 2, 4]$$$,将写入数组 $$$[1, 2, 2]$$$ 和 $$$[4]$$$。