Ngủ Trong Lớp

Bessie hay ngủ gật trong lớp, và bạn thân Elsie đã ghi lại số lần Bessie ngủ gật trong mỗi tiết học. Nhật ký gồm $N$ tiết học, tiết thứ $i$ Bessie ngủ gật $a_i$ lần.

Elsie muốn chỉnh sửa nhật ký sao cho tất cả các tiết đều có số lần ngủ gật bằng nhau. Mỗi thao tác chỉnh sửa cho phép Elsie chọn hai tiết liền kề, gộp chúng lại thành một tiết duy nhất (số lần ngủ gật của tiết mới bằng tổng hai tiết cũ), đồng thời giảm tổng số tiết đi 1.

Hãy tìm số thao tác gộp tối thiểu để tất cả các tiết còn lại có số lần ngủ gật bằng nhau.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test
• Với mỗi bộ test:
  • Dòng 1: Số nguyên $N$ — số tiết học
  • Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — số thao tác gộp tối thiểu.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le {10}^5$, tổng $N$ qua các bộ test $\le {10}^5$
• $0\le a_i\le {10}^6$, tổng $a_i$ qua tất cả các tiết $\le {10}^6$

Ví dụ