Sau khi kết thúc giãn cách xã hội, cô bò Bessie rất hào hứng khi được quay trở lại học trực tiếp. Tuy nhiên, thầy giáo của cô, thầy John, lại là một giáo viên giảng bài không được lôi cuốn cho lắm. Vì vậy cô ta thường xuyên ngủ gật trong lớp.

Thầy John đã nhận ra Bessie thường xuyên không tập trung trong giờ học. Vì vây, thầy đã nhờ Elsie, một bạn học sinh khác trong lớp, theo dõi số lần Bessie ngủ gật trong từng tiết. Có ~N~ tiết học ~(1 \le N \le 10^5)~, và Elsie thống kê được Bessie đã ngủ gật ~a_i~ lần ~(0 \le a_i \le 10^6)~ trong tiết học thứ ~i~. Tổng số lần Bessie ngủ gật trong tất cả các tiết tối đa là ~10^6~.

Elsie, vốn không thích chơi với Bessie, muốn thầy John nghĩ rằng Bessie luôn có số lần ngủ gật giống nhau trong tất cả các tiết (vì vậy sẽ làm cho thầy thấy rằng vấn đề là do Bessie, không phải do thầy bài giảng của thầy chán). Cách duy nhất để Elsie chỉnh sửa thống kê của mình trước khi gửi thầy, đó là kết hợp hai tiết học liên kề với nhau. Ví dụ, nếu ~a=[1,2,3,4,5]~, sau đó Elsie kết hợp tiết học thứ hai và thứ ba, bản thống kê sẽ trở thành ~[1,5,4,5]~.

Bạn hãy giúp Elsie tính số lần chỉnh sửa bản thống kê ít nhất để cô có thể làm cho tất cả số trong bản thống kê bằng nhau.

Dữ liệu vào

• Mỗi bộ dữ liệu vào sẽ chứa ~T~ ~(1 \le T \le 10)~ bộ test độc lập với nhau.
• Dòng đầu tiên chứa số nguyên ~T~ - số bộ test. Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên chứa số nguyên ~N~.
  • Dòng tiếp theo chứa ~a_1, a_2, \dots, a_N~.

Dữ liệu vào đảm bảo, trong mỗi bộ test, tổng các giá trị của mảng ~a~ không vượt quá ~10^6~. Và tổng các giá trị ~N~ của tất cả các bộ test không vượt quá ~10^5~.

Dữ liệu ra

In ra T dòng, mỗi dòng ghi số lần chỉnh sửa ít nhất có thể của bộ test tương ứng.

Sample Input

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

Sample Output

3
2
0

Giải thích

Ở bộ test đầu tiên của ví dụ, Elsise có thể sửa bản thống kê ~3~ lần để có các giá trị toàn là ~3~.

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

Ở bộ test thứ hai, Elsie có thể sửa bản thống kê ~2~ lần để có một số ~7~.

   2 2 3
-> 2 5
-> 7

Ở bộ test cuối cùng, Elsie không cần chỉnh sửa gì vì bản thống kê đã chứa các giá trị bằng nhau (bằng ~0~).

Credits bài tập: Jesse Choe