Bò Bessie rất hào hứng vì gần đây đã được quay lại học trực tiếp! Đáng tiếc, giáo viên của cô, Farmer John, giảng bài rất nhàm chán nên cô thường xuyên ngủ gật trong lớp.

Farmer John nhận thấy Bessie không chú ý trong giờ học. Ông nhờ một học sinh khác trong lớp là Elsie ghi lại số lần Bessie ngủ gật trong mỗi buổi học. Có \(N\) buổi học (\(1\le N\le 10^5\)), và Elsie ghi nhận rằng Bessie ngủ gật \(a_i\) lần (\(0\le a_i\le 10^6\)) trong buổi học thứ \(i\). Tổng số lần Bessie ngủ gật trong tất cả các buổi học không vượt quá \(10^6\).

Vì rất thích cạnh tranh với Bessie, Elsie muốn khiến Farmer John nghĩ rằng Bessie luôn ngủ gật cùng một số lần trong mọi buổi học — qua đó làm cho vấn đề có vẻ hoàn toàn là lỗi của Bessie, không phụ thuộc vào những bài giảng đôi khi nhàm chán của Farmer John. Cách duy nhất Elsie được phép sửa nhật ký là gộp hai buổi học kề nhau. Ví dụ, nếu \(a=[1,2,3,4,5]\) và Elsie gộp buổi học thứ hai với buổi học thứ ba, nhật ký sẽ trở thành \([1,5,4,5]\).

Hãy giúp Elsie tính số lần sửa nhật ký ít nhất cần thực hiện để tất cả các số trong nhật ký bằng nhau.

Dữ liệu vào

Mỗi tệp vào chứa \(T\) (\(1\le T\le 10\)) bộ test cần được giải độc lập.

Dòng đầu tiên chứa \(T\), số bộ test cần giải. Sau đó là \(T\) bộ test, mỗi bộ được mô tả bởi hai dòng. Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\).

Trong mỗi bộ test, tổng mọi giá trị trong \(a\) không vượt quá \(10^6\). Đồng thời, tổng \(N\) trên tất cả các bộ test không vượt quá \(10^5\).

Dữ liệu ra

In ra \(T\) dòng; với mỗi bộ test, dòng tương ứng là số lần sửa ít nhất Elsie có thể thực hiện để mọi phần tử của nhật ký bằng nhau.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

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

3
2
0

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

   2 2 3
-> 2 5
-> 7

Nguồn

USACO 2022 February Contest, Bronze — Sleeping in Class: https://usaco.org/index.php?page=viewproblem2&cpid=1203

Tác giả: Jesse Choe.