נתונה לך סדרת מספרים שלמים באורך $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