울타리

바이타자르는 이 지역에서 가장 인색한 사람으로 널리 알려져 있다. 그 증거는 많지만, 가장 사소한 예는 그의 부지에 울타리가 아예 없다는 점이다. 그러나 최근 지하실에서 오래된 널빤지 $n$개를 찾아냈기 때문에, 울타리의 일부라도 세우기로 했다.

그는 널빤지를 쌓아 올려 위에서부터의 길이가 차례로 $a_1, \ldots, a_n$이 되도록 했다. 첫 번째 널빤지에서 길이 $b$인 조각을 잘라 울타리의 가장 왼쪽에 못으로 박았다. 그다음 길이 $b$인 조각을 또 잘라 앞의 조각 옆에 박았다. 손에 남은 조각의 길이가 $c$($1 \leq c \leq b$)가 될 때까지 이 과정을 반복했다. 그 짧은 조각도 이렇게 좋은 널빤지를 버리기 아깝다며 울타리에 박았다. 그다음 더미에서 두 번째 널빤지를 꺼내 같은 과정을 되풀이했고, 모든 널빤지에 대해 같은 방식으로 처리했다.

작업이 끝나자 그는 짧은 조각을 쓴 것이 좋은 생각이 아니었다고 판단했다. 울타리 전체를 흰색으로 칠했지만, 왼쪽 끝부터 한 장씩 건너뛰며 칠하면 페인트가 거의 절반만 들고도 여전히 짜임새 있어 보인다는 것을 알아챘다. 그래서 왼쪽 끝 널빤지부터 두 번째마다 하나씩만 칠했다. (사실 두 번째 널빤지부터 시작해도 되었다.)

그날 밤 그는 다른 높이 $b$를 골랐다면 페인트가 덜 들었을지 궁금해졌다. 가능한 모든 높이 $b = 1, \ldots, M$에 대해 ($M$은 $a_i$의 최댓값) 흰색으로 칠해야 할 널빤지 길이의 총합을 구하라.

첫 줄에 테스트 케이스의 개수 $z$($1 \leq z \leq 5$)가 주어진다.

각 테스트 케이스의 첫 줄에는 널빤지의 개수 $n$($1 \leq n \leq 1\,000\,000$)이 주어진다. 이어서 널빤지 길이 $a_1, \ldots, a_n$을 나타내는 정수 $n$개가 주어진다($1 \leq a_i \leq 1\,000\,000$, $\sum_{i=1}^n a_i \leq 1\,000\,000$).

각 테스트 케이스마다 $M$줄을 출력한다. $M$은 해당 테스트 케이스에서 $a_i$의 최댓값이다. $i$번째 줄에는 높이를 $b = i$로 정했을 때 바이타자르가 흰색으로 칠했을 널빤지 길이의 총합 $f_i$를 출력한다.

높이 $b = 4$일 때 울타리 조각은 4 4 2 4 3 2 4 4가 된다. 칠하는 조각의 길이 합은 $4 + 2 + 3 + 4 = 13$이므로, 4번째 줄의 답은 13이다.

높이 $b = 5$일 때 울타리 조각은 5 5 5 2 2 5 3이 된다. 칠하는 조각의 길이 합은 $5 + 5 + 2 + 3 = 15$이므로, 5번째 줄의 답은 15이다.