Misaka Mikoto היא בעלת הכוחות בדרגה 5 המדורגת שלישית ב־Academy City, וכינויה Railgun נובע מהמהלך האופייני שלה. יום אחד פולשים כמה רובוטים מרושעים ל־Academy City, ו־Misaka מתכננת להשמיד את כולם.

נתייחס ל־Academy City כמישור דו־ממדי. יש בסך הכול $n$ רובוטים, ומיקומו של הרובוט ה־$i$ הוא $(x_i,y_i)$.‏ Misaka תתחיל לנוע מ־$(0,0)$, ויכולת ה־Railgun שלה תשמיד את כל הרובוטים שחולקים איתה את קואורדינטת $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)$.