수업시간에 잠자기

지니는 대학에서 컴퓨터 과학 강의를 듣고 있습니다. 그런데 강의가 때때로 지루해서 그는 종종 강의 도중 잠을 자곤 합니다.

교수님은 지니가 수업 중에 주의를 기울이지 않고 있다는 것을 알아차렸습니다. 그래서 교수님이 다른 학생 토미에게 지니가 수업 동안 몇 번이나 잠을 잤는지 기록하라고 부탁했습니다. 총 $N$회의 강의 기간이 있으며 ($1 \le N \le 10^5$), 토미는 지니가 $i$-번째 강의에서 $a_i$번 잠을 잤다고 기록하였습니다. ($0 \le a_i \le 10^6$) 모든 강의 기간 동안 지니가 잠을 잔 횟수의 총합은 $10^6$을 초과하지 않습니다.

토미는 경쟁 심리로 지니가 모든 강의에서 일관되게 잠을 자는 것처럼 보이게 하고 싶습니다. 이렇게 하면 문제가 교수님의 강의 스타일 때문이 아니라 완전히 지니의 탓이라고 생각할 것이기 때문입니다. 토미는 기록을 수정할 수 있는 유일한 방법은 두 개의 인접한 강의 기간을 합치는 것입니다. 예를 들어, $a=[1,2,3,4,5]$이면 토미는 두 번째와 세 번째 강의 기간을 합쳐서 기록을 $[1,5,4,5]$로 바꿀 수 있습니다.

토미가 로그의 모든 숫자를 동일하게 만들려면 로그를 최소 몇 번 수정해야 하는지 계산하여 도와주세요.

각 입력에는 $T$ ($1 \le T \le 10$) 테스트 케이스가 포함되며, 각 테스트 케이스는 독립적으로 해결해야 합니다.

첫 번째 줄에는 테스트 케이스의 수 $T$가 주어집니다. 그 후에 $T$개의 테스트 케이스가 주어지며, 각각 두 줄로 구성됩니다. 각 페어의 첫 번째 줄에는 $N$이 주어지며, 두 번째 줄에는 $a_1, a_2, \ldots, a_N$이 주어집니다.

각 테스트 케이스 내에서 $a$의 모든 값의 합계가 최대 $10^6$을 초과하지 않도록 보장됩니다. 또한 모든 테스트 케이스에 대한 $N$의 합은 최대 $10^5$을 초과하지 않습니다.

출력으로 $T$개의 줄을 작성하여 각 케이스에 대해 토미가 모든 로그 항목을 동일하게 만들기 위해 수행해야 할 최소 수정 횟수를 나타내십시오.