#P18084. Split Sticks

Split Sticks

Split Sticks

题目描述

有 nn 根木棍从左到右排列,第 ii 根的长度为正整数 aia_i。一次操作依次执行:

  1. 选择一根木棍,将其切成长度均为整数的左、右两部分,允许其中一部分长度为 00。
  2. 把左半部分合并到原木棍左边紧邻的木棍上;如果左边没有木棍,则左半部分独立成为一根木棍。
  3. 把右半部分合并到原木棍右边紧邻的木棍上;如果右边没有木棍,则右半部分独立成为一根木棍。
  4. 删除所有长度为 00 的木棍。

求使剩余木棍长度全部相等的最少操作次数。剩余木棍的数量可以改变。可以证明总存在可行操作序列。

输入格式

第一行一个整数 tt,表示测试组数。每组第一行一个整数 nn,第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

1≤t≤1051\le t\le10^5,1≤n≤1061\le n\le10^6,1≤ai≤1061\le a_i\le10^6;所有组的 nn 之和不超过 10610^6。

输出格式

每组输出一行一个整数,表示最少操作次数。

样例输入

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

样例输出

1
2
0