D. Прибавления в соседей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарпу подарили массив $$$a[1 \dots n]$$$ из $$$n$$$ целых чисел. Он может производить с массивом $$$a$$$ следующую операцию не более $$$n$$$ раз:

  • Поликарп выбирает индекс $$$i$$$ и прибавляет в одного на свой выбор из его соседей значение $$$a_i$$$. Более формально, Поликарп прибавляет значение $$$a_i$$$ либо к $$$a_{i-1}$$$, либо к $$$a_{i+1}$$$ (если такого соседа не существует, то и прибавить в него нельзя);
  • После прибавления Поликарп удаляет $$$i$$$-й элемент из массива $$$a$$$ (заметим, что в процессе удаления длина массива $$$a$$$ уменьшается на $$$1$$$).

Два пункта выше совместно обозначают одну операцию.

Например, если у Поликарпа есть массив $$$a = [3, 1, 6, 6, 2]$$$, то он может произвести с ним следующую последовательность операций:

  • Поликарп выбирает $$$i = 2$$$ и прибавляет значение $$$a_i$$$ к $$$(i-1)$$$-у элементу: $$$a = [4, 6, 6, 2]$$$;
  • Поликарп выбирает $$$i = 1$$$ и прибавляет значение $$$a_i$$$ к $$$(i+1)$$$-у элементу: $$$a = [10, 6, 2]$$$;
  • Поликарп выбирает $$$i = 3$$$ и прибавляет значение $$$a_i$$$ к $$$(i-1)$$$-у элементу: $$$a = [10, 8]$$$;
  • Поликарп выбирает $$$i = 2$$$ и прибавляет значение $$$a_i$$$ к $$$(i-1)$$$-у элементу: $$$a = [18]$$$;

Заметьте, что Поликарп мог прекратить производить операции в любой из моментов.

Поликарпу стало интересно, сколько минимум операций ему надо произвести, чтобы все элементы массива $$$a$$$ стали одинаковыми (то есть, он хочет, чтобы все $$$a_i$$$ были равны между собой).

Входные данные

В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 3000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 3000$$$) — длина массива. В следующей строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — минимальное количество операций, которые нужно сделать Поликарпу, чтобы все элементы массива $$$a$$$ оказались одинаковыми.

Пример
Входные данные
4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1
Выходные данные
4
2
0
2
Примечание

В первом наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):

$$$[3, 1, 6, 6, 2]$$$ $$$\xrightarrow[]{i=4,~прибавляет~влево}$$$ $$$[3, 1, 12, 2]$$$ $$$\xrightarrow[]{i=2,~прибавляет~вправо}$$$ $$$[3, 13, 2]$$$ $$$\xrightarrow[]{i=1,~прибавляет~вправо}$$$ $$$[16, 2]$$$ $$$\xrightarrow[]{i=2,~прибавляет~влево}$$$ $$$[18]$$$. Все элементы в массиве $$$[18]$$$ одинаковые.

Во втором наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):

$$$[1, 2, 2, 1]$$$ $$$\xrightarrow[]{i=1,~прибавляет~вправо}$$$ $$$[3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~прибавляет~влево}$$$ $$$[3, 3]$$$. Все элементы в массиве $$$[3, 3]$$$ одинаковые.

В третьем наборе входных данных Поликарпу не надо производить ни одну операцию, так как массив $$$[2, 2, 2]$$$ уже содержит одинаковые элементы.

В четвертом наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):

$$$[6, 3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~прибавляет~вправо}$$$ $$$[6, 3, 3]$$$ $$$\xrightarrow[]{i=3,~прибавляет~влево}$$$ $$$[6, 6]$$$. Все элементы в массиве $$$[6, 6]$$$ одинаковые.