题目描述

$T$ 组数据，每组给定一个长度为 $N$ 的数组 $a_1, a_2, \dotsb , a_n$。

每次操作可选择两个相邻的数合并，得到的新数为两者之和。

求最少操作次数使得所有数相等。

数据范围： $1 \leq T \leq 10, \sum a_i \leq 10 ^ 6, \sum N \leq 10 ^ 51≤T≤10$

输入格式

一行一个整数 $T$。

接下来 $T$ 组数据，每组数据第一行一个整数 $N$，第二行 $N$ 个整数，$a_1, a_2, \dotsb , a_n$，含义如题目描述。

输出格式

$T$ 行，每行一个整数，表示最少操作次数。可证明总存在一种操作满足题意。