لديك متتالية أعداد صحيحة طولها $n$: $a_1, a_2, \dots, a_n$. يمكنك إجراء العملية التالية مرة واحدة بالضبط:

• اختر تبديلاً $p_1, p_2, \dots, p_n$ للأعداد $1, 2, \dots, n$.
• ثم، من أجل $i$ من $1$ إلى $n$ بالترتيب الطبيعي، نفّذ: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ حيث $a_0 = 0$ و $a_{n+1} = 0$.

هدفك هو تعظيم مجموع جميع العناصر في المتتالية بعد اكتمال العملية.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $t$ ($1 \le t \le 10^4$)، وهو عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول على عدد صحيح $n$ ($1 \le n \le 2 \cdot 10^5$).

يحتوي السطر الثاني على $n$ أعداد صحيحة $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

لا يتجاوز مجموع $n$ القيمة $2 \cdot 10^5$.

الإخراج

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

مثال

الإدخال

4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3

الإخراج

22
85
72
79