엘리베이터 정차 층 정하기

큰 대학 건물의 지상층에서 학생 여러 명이 엘리베이터를 기다린다. 이 층을 0층이라 부르고, 그 위의 층을 아래에서부터 1층, 2층, $\dots$, $n$층이라 부른다. 엘리베이터는 0층에서 출발해 위로만 올라간다.

보통은 내릴 학생이 있는 모든 층에 멈춘다. 그러면 더 높은 층까지 가려는 학생은 그 정차마다 짜증이 난다. 반대로 어떤 층을 건너뛰면 그 층에서 내리려던 학생이 짜증이 난다.

짜증은 이렇게 센다. 학생은 자기가 내릴 층에 엘리베이터가 아직 도착하지 않은 상태에서 엘리베이터가 멈추는 층마다 짜증이 난다. 엘리베이터가 자기가 내릴 층을 건너뛰면, 그 층부터 엘리베이터가 다음으로 멈추는 층의 바로 아래 층까지 층마다 짜증이 난다. 다음 정차 층에서 내려 계단으로 걸어 내려가면 그때 짜증이 끝난다.

예를 들어 5층에서 내리려는 학생이 있고 엘리베이터가 2층, 7층, 10층에 멈춘다면 이 학생은 2층, 5층, 6층에서 짜증이 나므로 모두 세 개 층에서 짜증이 난다.

엘리베이터에 타면 학생은 모두 자기가 갈 층의 버튼을 누른다. 다른 사람이 이미 누른 버튼도 다시 누른다. 그래서 엘리베이터를 제어하는 CPU는 각 층에서 내리려는 학생 수를 정확히 안다.

어느 층에 멈출지 정하는 프로그램을 작성한다. 목표는 짜증의 총합, 즉 모든 학생이 짜증이 난 층의 개수를 전부 더한 값을 최소로 만드는 것이다.

더 높은 층에서 타려는 사람은 모두 무시한다. 0층에서 기다리는 학생은 누구나 자기가 가려는 층에서 내리거나, 그보다 위의 정차 층에서 내려 계단으로 걸어 내려가서 목적지에 도착할 수 있어야 한다.

첫 줄에 테스트 케이스의 개수가 주어진다. 이 값은 양수이고 100 이하이다. 그다음 각 테스트 케이스마다 다음이 주어진다.

• 첫 줄에 정수 $n$ ($1 \le n \le 1500$). 0층을 제외한 건물의 층 수이다.
• 다음 줄에 공백으로 구분된 정수 $n$개 $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 1500$). $s_i$는 $i$층에서 내리려는 학생 수이다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 짜증의 총합이 될 수 있는 최솟값이다.