Бесі тішилася запровадженням індивідуального навчання. На жаль, її тьютор Фермер Джон, дуже нудний лектор, і тому вона часто засинала на заняттях.

ФД це помітив і попросив Ельзу вести облік засипань Бесі. Усього є \(N\) (\(1\le N\le 10^5\)) періодів, коли проходили заняття. І Ельза записала, що Бесі засинала \(a_i\) (\(0\le a_i\le 10^6\)) раз на час \(і\)-го періоду. Загальна кількість засипань Бєсі не перевищує \(10^6\).

Ельза хоче показати ФД, що Бесі завжди засипала однакову кількість разів. Але єдиний спосіб, яким вона це може зробити - об'єднати два сусідніх періодів проведення занять. Наприклад, якщо \(a=[1,2,3,4,5],\) Ельза може об'єднати другий і третій періоди та лог стане таким \([1,5,4,5]\).

Допоможіть Ельзі обчислити мінімальну кількість модифікацій лога, які вона повинна зробити, щоб зробити всі числа лога рівними.

Формат вхідних даних

Кожне введення містить \(T\) (\(1\le T\le 10\)) тестів, які потрібно вирішувати незалежно.

Перший рядок містить \(T\) - кількість тестів. Потім слідують \(T\) тестів, кожен описується парою рядків. Перший рядок пари містить \(N\), а другий містить \(a_1,a_2,\ldots,a_N\).

Гарантується, що всередині кожного тесту сума всіх \(a_i\) не перевищує \(10^6\). Також гарантується, що сума всіх \(N\) у цих тестах не перевищить \(10^5\).

Формат вихідних даних

Виведіть \(T\), що містять мінімальну кількість модифікацій, що може виконати Ельза, щоб зрівняти всі числа у логах для кожного тесту.

Приклад вхідних даних

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

Приклад вихідних даних

3
2
0

Для першого тесту достатньо 3 модифікацій

    1 2 3 1 1 1
    3 3 1 1 1
    3 3 2 1
    3 3 3

Для другого тесту достатньо двох модифікацій

    2 2 3
    2 5
    7

Для останнього тесту модифікацій не потрібно, тому що всі числа вже рівні.

Автор: Jesse Choe