C. Минимизируй толщину
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана последовательность $$$a=[a_1,a_2,\dots,a_n]$$$, состоящая из $$$n$$$ положительных целых чисел.

Назовём её подотрезком группу подряд идущих элементов. Каждый подотрезок характеризуется двумя индексами — индексом своего начала и индексом своего окончания. Обозначим за $$$a[l,r]$$$ подотрезок последовательности $$$a$$$ с началом в $$$l$$$ и концом в $$$r$$$, то есть $$$a[l,r]=[a_l, a_{l+1}, \dots, a_r]$$$.

Например, если $$$a=[31,4,15,92,6,5]$$$, то $$$a[2,5]=[4,15,92,6]$$$, $$$a[5,5]=[6]$$$, $$$a[1,6]=[31,4,15,92,6,5]$$$ — её подотрезки.

Разобьем заданную последовательность $$$a$$$ на подотрезки так, чтобы:

  • каждый элемент попал ровно в один подотрезок;
  • суммы элементов для всех подотрезков равны.

Например, если $$$a$$$ = [$$$55,45,30,30,40,100$$$], то такую последовательность можно разбить на три подотрезка: $$$a[1,2]=[55,45]$$$, $$$a[3,5]=[30, 30, 40]$$$, $$$a[6,6]=[100]$$$. Каждый элемент принадлежит ровно одному подотрезку, сумма элементов каждого подотрезка равна $$$100$$$.

Назовём толщиной разбиения длину самого длинного подотрезка. Например, толщина разбиения из примера выше равна $$$3$$$.

Найдите минимальную толщину среди всевозможных разбиений заданной последовательности $$$a$$$ на подотрезки требуемым образом.

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

В первой строке вам дано единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Каждый набор входных данных описывается двумя строками.

В первой строке каждого набора входных данных содержится единственное целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — длина последовательности $$$a$$$.

Во второй строке каждого набора входных данных содержится ровно $$$n$$$ целых чисел: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы последовательности $$$a$$$.

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

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

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

Обратите внимание, что всегда существует разбиение, вы всегда можете рассматривать всю последовательность как один подотрезок.

Пример
Входные данные
4
6
55 45 30 30 40 100
4
10 23 7 13
5
10 55 35 30 65
6
4 1 1 1 1 4
Выходные данные
3
4
2
3
Примечание

Разбиение в первом наборе входных данных рассмотрено в условии, можно показать, что оно оптимально.

Во втором наборе входных данных разбить на подотрезки можно только оставив единственный подотрезок. Тогда толщина разбиения равна длине всей последовательности, то есть $$$4$$$.

В третьем наборе входных данных оптимальным будет разбиение $$$[10, 55], [35, 30], [65]$$$. Толщина разбиения будет равна $$$2$$$.

В четвёртом наборе возможны следующие разбиения:

  • $$$[4] + [1, 1, 1, 1] + [4]$$$;
  • $$$[4, 1, 1] + [1, 1, 4]$$$.