문제
오늘도 열심히 수업을 들으러 온 준이는 피곤했는지 수업 시간 동안 자주 졸았다.
권수쌤은 준이가 수업 시간에 집중을 하지 못하고 꾸벅꾸벅 졸고 있다는 사실을 알아차렸다!
그래서 현이에게 준이가 잠든 횟수를 기록해 달라고 요청했다.
수업 시간은 총 N시간(1≤N≤105)으로 현이는 i번째 수업시간에 준이가 ai(0≤ai≤106) 잠들었다고 기록했다. 다행히(?) 준이는 모든 수업을 합쳐 최대 106번 이상 잠들지는 않는다.
현이는 준이와 라이벌이라고 생각했기에 권수쌤이 준이가 모든 수업에서 항상 같은 횟수만큼 꾸준히 잠들고 있는 성실하게 불량한 학생이라고 생각하도록 하고 싶었다.
현이가 기록을 수정할 수 있는 유일한 방법은 인접한 두 수업 시간을 병합하는 것이다.
예를 들어, a=[1,2,3,4,5]인 경우 현이가 두 번째 시간과 세 번째 시간을 병합하면 기록은 [1,5,4,5]가 된다.
현이가 기록의 모든 숫자를 동일하게 만들 수 있도록 기록에 적용해야 하는 최소 변경 수를 계산하는 프로그램을 작성하시오.
입력
각 테스트 케이스는 독립적으로 해결해야 하는 T(1≤T≤10)개의 하위 테스트 케이스를 포함한다.
입력의 첫 번째 줄에는 해결할 하위 테스트 케이스의 수인 T가 입력된다.
그 다음 줄부터는 T번에 걸쳐 각각 두 줄씩 첫 번째 행은 N, 두 번째 행은 a1, a2, …, aN이 입력된다.
각 하위 테스트 케이스에서 모든 숫자의 합이 106을 초과하지 않음이 보장된다.
또한 모든 하위 테스트 케이스의 N 합계가 105를 초과하지 않음이 보장된다.
출력
각 하위 테스트 케이스 별로 현이가 기록의 모든 숫자를 동일하게 만드는 데 필요한 최소 수정 횟수를 출력하시오.
예제1
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
3
2
0