يقف 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$.