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$