\begin{problem}{Кризис на планете Шелезяка}{стандартный ввод}{стандартный вывод}{1 секунда}{256 мегабайт}

\textit{Полезных ископаемых нет. Воды нет. Растительности нет. Населена роботами.}

День на планете Шелезяка длится $n$ часов. Каждый робот, обитающий на этой планете, очень трудолюбивый. За день он по порядку перетаскивает $n$ ящиков массой $a_1, a_2, \ldots, a_n$, по ящику в час. Затем наступает следующий день, и он снова перетаскивает ящики массой $a_1, a_2, \ldots, a_n$. Ровно \textbf{один раз} в день между перетаскиваниями ящиков робот получает порцию смазки.

Механизмы роботов очень чувствительны, поэтому каждый перетащенный ящик наносит роботу урон. Ящик с номером $i$ \textbf{моментально} нанесёт $a_i$ урона за каждый час, начиная с $i$ до следующего получения смазки. Обратите внимание, что смазка может быть получена на следующий день.

Например, если $n = 8$, а мы выдали роботам смазку после перетаскивания $5$-го ящика:
\begin{itemize}
\item Ящик $a_5$ нанесёт урон один раз (всего $a_5$ урона);
\item Ящик $a_6$ нанесёт урон восемь раз (всего $a_6 \cdot 8$ урона);
\item Ящик $a_2$ нанесёт урон четыре раза (всего $a_2 \cdot 4$ урона).
\end{itemize}

Вы можете выбрать момент, в который робот будет получать порцию смазки каждый день. Посчитайте \textbf{минимальный} урон, который будет нанесён роботу за один день при оптимальном выборе этого момента.

\begin{center}
\includegraphics{tri2.png}
\end{center}


\InputFile
В первой строке вводится целое число $t$ ($1 \le t \le 1000$) --- количество наборов входных данных.

Далее следует описание наборов.

В первой строке каждого набора вводится целое число $n$ ($1 \le n \le 2\cdot 10^5$) --- количество перетаскиваний ящиков.

Во второй строке каждого набора вводится $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^7$) --- массы ящиков. 

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2\cdot 10^5$.


\OutputFile
Для каждого набора входных данных выведите минимальный урон, который может получить робот за один день.


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
Разберём первый набор входных данных:

Если выдать смазку перед первым ящиком, $a_1$ урона нанесётся пять раз, $a_2$ урона нанесётся четыре раза и т.д., то есть суммарный урон будет равен: $5 \cdot a_1 + 4 \cdot a_2 + 3 \cdot a_3 + 2 \cdot a_4 + 1 \cdot a_5 = 15 + 32 + 3 + 14 + 4 = 68$.

Если выдать смазку после первого ящика, суммарный урон будет равен: $1 \cdot a_1 + 5 \cdot a_2 + 4\cdot a_3 + 3 \cdot a_4 + 2\cdot a_5 = 3 + 40 + 4 + 21 + 8 = 76$.

Если выдать смазку после второго ящика, суммарный урон будет равен: $6 + 8 + 5 + 28 + 12 = 59$.

После третьего ящика: $9 + 16 + 1 + 35 + 16 = 77$.

После четвёртого ящика: $12 + 24 + 2 + 7 + 20 = 65$.

Выдача смазки после пятого ящика эквивалентна выдаче смазки перед первым ящиком.

Таким образом, минимальный урон равен $59$.


\end{problem}

