수업 시간에 졸기

소 Bessie는 최근 대면 수업으로 돌아와서 신이 났다! 안타깝게도 담당 강사 Farmer John의 수업은 매우 지루해서, Bessie는 수업 시간에 자주 잠이 든다.

Farmer John은 Bessie가 수업에 집중하지 않는다는 것을 알아챘다. 그는 같은 반 학생 Elsie에게 특정 수업에서 Bessie가 잠든 횟수를 기록해 달라고 부탁했다. 수업 시각은 $N$개 있고($1\le N\le 10^5$), Elsie는 $i$번째 수업 시각에 Bessie가 $a\_i$번 잠들었다고 기록했다($0\le a\_i\le 10^6$). 모든 수업 시각에 걸쳐 Bessie가 잠든 총 횟수는 $10^6$ 이하이다.

Bessie에게 매우 경쟁심을 느끼는 Elsie는 Farmer John이 Bessie가 모든 수업에서 항상 같은 횟수만큼 잠든다고 느끼게 만들고 싶어 한다. 즉, 문제가 전적으로 Bessie의 잘못인 것처럼 보이게 하고, Farmer John의 때때로 지루한 수업과는 무관하다는 인상을 주려는 것이다. Elsie가 기록을 수정할 수 있는 유일한 방법은 인접한 두 수업 시각을 합치는 것이다. 예를 들어 $a=\[1,2,3,4,5]$라면, Elsie가 두 번째와 세 번째 수업 시각을 합칠 때 기록은 $\[1,5,4,5]$가 된다.

기록의 모든 수가 같아지도록 만들기 위해 Elsie가 해야 하는 최소 수정 횟수를 구하는 것을 도와주자.

각 입력은 독립적으로 해결해야 하는 $T$개의 테스트 케이스로 이루어진다($1\le T\le 10$).

첫 번째 줄에는 해결해야 하는 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 각각 두 줄로 주어진다. 각 쌍의 첫 번째 줄에는 $N$이 주어지고, 두 번째 줄에는 $a\_1,a\_2,\ldots,a\_N$이 주어진다.

각 테스트 케이스에서 $a$의 모든 값의 합은 $10^6$ 이하임이 보장된다. 또한 모든 테스트 케이스에 걸친 $N$의 합은 $10^5$ 이하임이 보장된다.

각 테스트 케이스마다 기록의 모든 항목이 같아지도록 Elsie가 수행할 수 있는 최소 수정 횟수를 한 줄에 하나씩, 총 $T$줄에 걸쳐 출력한다.

이 예제의 첫 번째 테스트 케이스에서 Elsie는 3번의 수정으로 기록을 3으로만 이루어지게 바꿀 수 있다.

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

두 번째 테스트 케이스에서 Elsie는 2번의 수정으로 기록을 7로 바꿀 수 있다.

   2 2 3
-> 2 5
-> 7

마지막 테스트 케이스에서 Elsie는 아무 연산도 할 필요가 없다. 기록이 이미 같은 항목으로 이루어져 있다.