小P给了小O一个长为 的数组 ，初始数组中的每个数字都是白色。小O可以进行如下操作： 选择一个区间 ，满足 ，将区间所有元素染红。 小O想知道她最少几次操作可以将所有数字都染红，请你帮帮他吧。

输入描述:

每个测试文件均包含多个测试点。第一行输入一个整数 代表测试数据组数，每组测试数据描述如下：第一行输入一个整数  表示数组  的长度。第二行输入  个整数  表示数组  的元素。除此之外，保证所有的  的之和不超过  。

输出描述:

对于每一个测试点，在一行上输出一个正整数，表示染红所有数字的最小操作次数。