Little Cyan Fish נמצא על ציר המספרים. בהתחלה, הוא נמצא במיקום $a_0$, והבית שלו נמצא במיקום $0$.

הוא רוצה לבקר במיקומים $a_1, a_2, \ldots, a_n$ בסדר זה. הוא יכול ללכת לכל אחד מהכיוונים לאורך ציר המספרים. בכל עת, הוא יכול להשתגר לבית שלו או להעביר את הבית שלו למיקום הנוכחי שלו. שתי הפעולות הן בחינם וניתן לבצע אותן כל מספר של פעמים, כולל בזמן שהוא הולך.

מצאו את המרחק הכולל המינימלי שעליו ללכת כדי לבקר בכל המיקומים בסדר הנתון.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם יחיד $T$ ($1 \le T$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה מכילה מספר שלם יחיד $n$ ($1 \le n \le 5 \times 10^5$), המציין את מספר המיקומים שבהם יש לבקר. השורה השנייה מכילה $n + 1$ מספרים שלמים $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), המציינים את המיקום ההתחלתי ואת המיקומים שבהם יש לבקר.

מובטח כי סכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $5 \times 10^5$.

פלט

עבור כל מקרה בדיקה, הדפיסו שורה אחת המכילה מספר שלם יחיד, המציין את המרחק הכולל המינימלי שעל Little Cyan Fish ללכת.

דוגמאות

קלט 1

4
1
7 0
2
0 10 5
3
0 4 2 0
3
-2 3 -2 3

פלט 1

0
10
6
8

הערה

במקרה הבדיקה הראשון בדוגמה, Little Cyan Fish משתגר לבית שלו במיקום $0$, ולכן הוא אינו צריך ללכת.

במקרה הבדיקה השני בדוגמה, הוא הולך מ-$0$ אל $10$ ומעביר את הבית שלו למיקום $5$ בדרך. לאחר מכן הוא משתגר למיקום $5$. המרחק הכולל הוא $10$.

במקרה הבדיקה השלישי בדוגמה, הוא הולך מ-$0$ אל $4$ ומעביר את הבית שלו למיקום $2$ בדרך. לאחר מכן הוא משתגר אל $2$ והולך אל $0$. המרחק הכולל הוא $4 + 2 = 6$.

במקרה הבדיקה הרביעי בדוגמה, הוא משתגר אל $0$, הולך אל $3$, ומעביר את הבית שלו אל $3$. לאחר מכן הוא הולך אל $-2$ ומשתגר אל $3$. המרחק הכולל הוא $3 + 5 = 8$.