Misaka Mikoto เป็นผู้มีพลังจิต Level 5 อันดับสามใน Academy City และมีฉายาว่า Railgun จากท่าเฉพาะตัวของเธอ วันหนึ่ง หุ่นยนต์ชั่วร้ายหลายตัวบุก Academy City และ Misaka กำลังวางแผนกำจัดพวกมันทั้งหมด

มอง Academy City เป็นระนาบสองมิติ มีหุ่นยนต์ทั้งหมด $n$ ตัว และหุ่นยนต์ตัวที่ $i$ อยู่ที่ $(x_i,y_i)$ Misaka จะเริ่มเคลื่อนที่จาก $(0,0)$ และพลังเรลกันของเธอจะกำจัดหุ่นยนต์ทั้งหมดที่มีพิกัด $x$ หรือ $y$ ตรงกับเธอ กล่าวอย่างเป็นทางการ หาก Misaka อยู่ที่ $(x_m,y_m)$ หุ่นยนต์ทุกตัวที่มี $x_i=x_m$ หรือ $y_i=y_m$ จะถูกกำจัด

เนื่องจาก Misaka เกลียดทศนิยมและเรขาคณิตแบบยุคลิด เธอจะเคลื่อนที่จากจุดพิกัดจำนวนเต็มหนึ่งไปยังอีกจุดหนึ่งเท่านั้น และเคลื่อนที่ได้เฉพาะแนวนอน (ขนานกับแกน $x$) หรือแนวตั้ง (ขนานกับแกน $y$) เนื่องจากการเคลื่อนที่ไปรอบเมืองค่อนข้างเหนื่อย Misaka จึงขอให้คุณคำนวณระยะทางน้อยที่สุดที่เธอต้องเคลื่อนที่เพื่อกำจัดหุ่นยนต์ทั้งหมด

โปรดระลึกว่าจุดพิกัดจำนวนเต็มคือจุดที่ทั้งพิกัด $x$ และพิกัด $y$ เป็นจำนวนเต็ม

ข้อมูลนำเข้า

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็ม $T$ ระบุจำนวนกรณีทดสอบ สำหรับแต่ละกรณีทดสอบ:

บรรทัดแรกมีจำนวนเต็ม $n$ ($1 \le n \le 10^5$) ระบุจำนวนหุ่นยนต์

สำหรับ $n$ บรรทัดถัดไป บรรทัดที่ $i$ มีจำนวนเต็มสองจำนวน $x_i$ และ $y_i$ ($-10^9 \le x_i,y_i \le 10^9$) ระบุตำแหน่งหุ่นยนต์ตัวที่ $i$

รับประกันว่าผลรวมของ $n$ ในทุกกรณีทดสอบไม่เกิน $10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ พิมพ์หนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน ระบุระยะทางน้อยที่สุดที่ Misaka ต้องเคลื่อนที่เพื่อกำจัดหุ่นยนต์ทั้งหมด

ตัวอย่าง

ข้อมูลนำเข้า 1

3
2
0 1
1 0
4
1 1
-3 -3
4 -4
-2 2
4
1 100
3 100
-100 1
3 -100

ข้อมูลส่งออก 1

0
8
4

หมายเหตุ

สำหรับกรณีทดสอบตัวอย่างที่สอง Misaka ควรไปที่ $(0,1)$ ก่อน จากนั้นไป $(0,2)$ แล้วไป $(0,-3)$ และสุดท้ายไป $(0,-4)$

สำหรับกรณีทดสอบตัวอย่างที่สาม Misaka ควรไปที่ $(1,0)$ ก่อน จากนั้นไป $(1,1)$ แล้วไป $(3,1)$