• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک مهره‌ی اسب در خانه‌ی مرکزی یک جدول که از هر طرف نامتناهی است، قرار دارد. این مهره یک خانه را به عنوان مقصد خود انتخاب کرده است و می‌خواهد به سریع‌ترین روش ممکن به آن خانه‌ برسد. شما باید این کمترین تعداد حرکت ممکن را پیدا کنید.

به طور دقیق‌تر، در ابتدا اسب در خانه‌ی $(0,0)$ جدول قرار دارد شما باید حداقل تعداد حرکت مورد نیاز برای رفتن اسب به خانه‌ی $(x,y)$ را پیدا کنید.

مهره‌ی اسب در هر حرکت می‌تواند در یکی از جهت‌های عمودی یا افقی دو خانه به پیش برود و در جهت دیگر یک خانه به جلو برود. این هشت خانه‌ در شکل زیر با رنگ قرمز مشخص شده‌اند.

ورودی

در سطر اول ورودی، عدد طبیعی $t$ داده می‌شود. $$1\leq t \leq 3000$$

در سطر $i$ام از $t$ سطر بعدی، دو عدد $x_i$ و $y_i$ آمده است. $$0\leq x_i,y_i \leq 10^9$$

خروجی

پاسخ شما باید شامل $t$ خط باشد. در خط $i$ام باید حداقل حرکت مورد نیاز اسب برای رسیدن به $(x_i,y_i)$ با شروع از $(0,0)$ را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

6
1 1
2 1
2 2
3 3
3 1
2000 0

خروجی نمونه ۱

2
1
4
2
2
1000

• مسیر رسیدن اسب به خانه‌ی $(1,1)$ را می‌توانید در شکل زیر با توجه به اعداد صورتی پیدا کنید.
• مسیر رسیدن اسب به خانه‌ی $(2,1)$ را می‌توانید در شکل زیر با توجه به عدد قهوه‌ای پیدا کنید.
• مسیر رسیدن اسب به خانه‌ی $(2,2)$ را می‌توانید در شکل زیر با توجه به اعداد سیاه پیدا کنید.
• مسیر رسیدن اسب به خانه‌ی $(3,3)$ را می‌توانید در شکل زیر با توجه به اعداد بنفش پیدا کنید.
• مسیر رسیدن اسب به خانه‌ی $(3,1)$ را می‌توانید در شکل زیر با توجه به اعداد صورتی آبی پیدا کنید.