Беси радовалась введению индивидуального обучения.
К несчастью, её тьютор Фермер Джон, очень скучный лектор, и поэтому она
часто засыпала на занятиях.
ФД это заметил и попросил Эльзу вести учёт засыпаний Беси.
Всего имеется \(N\) (\(1\le N\le 10^5\)) периодов, когда проходили занятия.
И Эльза записала, что Беси засыпала \(a_i\) (\(0\le a_i\le 10^6\)) раз во время
\(i\)-го периода. Общее количество засыпаний Беси не превышает \(10^6\).
Эльза хочет показать ФД, что Беси всегда засыпала одинаковое количество раз.
Но единственный способ, которым она это может сделать - объединить два соседних
периода проведения занятий. Например, если \(a=[1,2,3,4,5],\) то Эльза может объединить
второй и третий периоды и лог станет таким \([1,5,4,5]\).
Помогите Эльзе вычислить минимальное количество модификаций лога, которые она должна
сделать, чтобы сделать все числа лога равными.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод содержит
\(T\) (
\(1\le T\le 10\)) тестов, которые нужно решать независимо.
Первая строка содержит \(T\) - количество тестов. Затем следуют \(T\) тестов,
каждый описывается парой строк. Первая строка пары содержит \(N\), а вторая
содержит \(a_1,a_2,\ldots,a_N\).
Гарантируется, что внутри каждого теста сумма всех \(a_i\) не превышает \(10^6\).
Также гарантируется, что сумма всех \(N\) в этих тестах не превысит \(10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\), содержащих минимальное число модификаций, которое может выполнить
Эльза, чтобы уравнять все числа в логах для каждого теста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
|
3
2
0
|