АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Болд урт гудамжинд байрлах дэлгүүрүүдээр хэсэхдээ үргэлж машинаа нэг газар байрлуулаад дараа нь орохоор төлөвлөсөн дэлгүүрүүдээрээ орж юмаа цуглуулаад эргээд машин руугаа буцдаг. Таны даалгавар бол Болдод хаана машинаа тавивал хамгийн бага зайг дэлгүүр хэсэхдээ явганаар туулахыг тооцоолж өгөх.

Урт гудамжин дахь дэлгүүрүүдийн  байрлалуудыг тоон шулуун дээрх бүхэл тоон координаттай цэгүүдээр  төлөөлүүлье. Тэр маш хүчирхэг тул цуглуулсан юмнуудаа замын турш өөрөө бариад явдаг.

Input

Оролтын эхний мөрөнд тестийн тоо t (1<=t<=100) өгөгдөнө.

Тест бүр 2 мөрөөс бүрдэнэ. Эхнийх нь Болдын орохоор төлөвлөж байгаа дэлгүүрийн тоо n (1<=n<=20), харин 2 дахь мөрөнд урт гудамжинд Болдын орохоор төлөвлөсөн дэлгүүрүүдийн тоон шулуун дээрх координат x_i   (0<=x_i<=99) бүхэл тоогоор өгөгдөнө.

Output

Тест бүрийн гаралт нэг мөр байна. Энэ нь Болдын машинаа хамгийн оновчтой зогсоолд байрлуулснаар явганаар туулах хамгийн богино зай болох бүхэл тоо байна.

Example

Input:

2

4

24 13 89 37

6

7 30 41 14 39 42

Output:

152

70