题目内容

产线质检得到一条长度为 $n$ 的整型读数序列 $v_1,v_2,\dots,v_n$。允许反复选取一对相邻读数，将其合并为一个新读数，新读数的值为两者之和。

需要使整条序列从左至右保持非降：任意相邻两项中，左侧读数的数值不超过右侧读数。

请计算达成上述目标所需的最少合并次数。

输入描述

首先一行一个正整数 $q$（表示随后有多少条记录）。

对于每条记录：

第一行一个正整数 $n$，表示该条记录中读数的个数。

第二行 $n$ 个正整数 $v_1,v_2,\dots,v_n$，表示读数序列。 $1 \le q \le 20$，$1 \le n \le 4\times 10^3$，$1 \le v_i \le 1000000000$

输出描述

按记录顺序，对每条记录各写出一行一个非负整数，表示该条记录对应的最少合并次数。

样例1

输入

3
3
2 1 3
4
1 2 3 4
3
5 1 6

输出

1
0
1

说明

第一条记录：将 $v_2$ 与 $v_3$ 合并，得到 $[2,4]$，已满足 $2 \le 4$，共合并 $1$ 次。

第二条记录：序列 $[1,2,3,4]$ 本身已单调不减，无需合并。

第三条记录：将 $v_1$ 与 $v_2$ 合并，得到 $[6,6]$，共合并 $1$ 次。

样例2

输入

1
5
3 2 1 4 5

输出

1

说明

将中间的 $v_2$ 与 $v_3$ 合并，得到 $[3,3,4,5]$，相邻读数依次为 $3 \le 3 \le 4 \le 5$，共合并 $1$ 次。