Monocarp 有一棵树,由 $$$n$$$ 个顶点组成,并以顶点 $$$1$$$ 为根。他决定研究 BFS(广度优先搜索),因此他在他的树上从根开始运行 BFS。 BFS可以用下面的伪代码来描述:
Monocarp 对 BFS 非常着迷,以至于最终他失去了他的树。幸运的是,他仍然有一个顶点序列,BFS 算法按照该顺序访问顶点(伪代码中的数组 a)。 Monocarp 知道每个顶点都被访问过一次(因为它们被放入队列并从队列中取出一次)。此外,他知道每个顶点的所有子节点都是按升序查看的。
Monocarp 知道有很多棵树(一般情况下)具有相同的访问顺序 $$$a$$$,所以他不希望恢复他的树。单果树适合任何高度最低的树。
树的高度是树顶点的最大深度,顶点的深度是从根到它的路径中的边数。例如,顶点 $$$1$$$ 的深度为 $$$0$$$,因为它是根,并且所有根的子节点的深度均为 $$$1$$$。
帮助 Monocarp 找到任意具有给定访问顺序 $$$a$$$ 和最小高度的树。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$; $$$a_i \neq a_j$$$; $$$a_1 = 1$$$) - BFS 算法访问顶点的顺序。
保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印具有给定访问顺序 $$$a$$$ 的树的最小可能高度。
示例
输入 #1
3 4 1 4 3 2 2 1 2 3 1 2 3
输出 #1
3 1 1
注意
在第一个测试用例中,只有一棵树具有给定的访问顺序:
在第二个测试用例中,也只有一棵树具有给定的访问顺序:
在第三个测试用例中,具有给定访问顺序的最优树如下所示: