يلعب السمكة السماوية الصغيرة لعبة Slay the Spire II وقد اختار شخصية «الصامتة» (Silent).

يحتاج السمكة السماوية الصغيرة الآن إلى قتال «صديق المعركة» (Battle Friend). في البداية، كل من طبقات «السم» (Poison) لدى صديق المعركة ومستوى «المُسرِّع» (Accelerant) لديك يساويان $0$. في كل جولة من الجولات الـ $n$ التالية، تحدث الأحداث التالية بالترتيب:

1. استخدام «السم القاتل» (Deadly Poison): زيادة طبقات السم لدى صديق المعركة بمقدار $x_i$.

2. اختيار ما إذا كنت ستستخدم «المُسرِّع»: اختر ما إذا كنت ستزيد مستوى المُسرِّع لديك بمقدار $1$.

3. تفعيل تأثير السم: بفرض أن مستوى المُسرِّع لديك هو $t$، كرر الحدث التالي $t$ من المرات:

   • لنفرض أن عدد طبقات السم لدى صديق المعركة هو $x$. إذا كان $x > 0$، فألحق ضررًا مقداره $x$ بصديق المعركة وقلل طبقات السم بمقدار $1$؛ وإلا، إذا كان $x = 0$، فلا يحدث شيء.

لاحظ أن كلاً من طبقات السم ومستوى المُسرِّع ينتقلان عبر الجولات ولا يختفيان.

يريد السمكة السماوية الصغيرة تعظيم إجمالي الضرر الملحق بصديق المعركة خلال هذه الجولات الـ $n$. يرجى طباعة قيمة هذا الضرر الأقصى.

الإدخال

يحتوي الإدخال على عدة حالات اختبار. السطر الأول من الإدخال يحتوي على عدد صحيح $T$ ($1 \le T$)، يمثل عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على عدد صحيح $n$ ($1 \le n \le 5000$).

يحتوي السطر الثاني على $n$ من الأعداد الصحيحة $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$)، تمثل عدد طبقات السم المضافة إلى صديق المعركة في كل جولة.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $10^6$، وأن مجموع $n^2$ عبر جميع حالات الاختبار لا يتجاوز $10^8$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على عدد صحيح يمثل أقصى إجمالي ضرر يمكن إلحاقه بصديق المعركة عبر جميع الجولات.

مثال

إدخال المثال 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

إخراج المثال 1

33
11
750
725