Košnja

Ο Mirko θέλει να αγοράσει γη στην οποία θα χτίσει ένα σπίτι για την οικογένειά του. Μέχρι στιγμής, έχει δει ~K~ κομμάτια γης. Καθένα από αυτά έχει σχήμα ορθογωνίου και μπορούμε να το σκεφτούμε ως πίνακα με ~N~ σειρές και ~M~ στήλες, ~N \times M~ πεδία συνολικά.

Ο Mirko γνωρίζει ότι, πριν ξεκινήσει η κατασκευή, το ακίνητο πρέπει να συντηρείται τακτικά και το γκαζόν πρέπει να κουρεύεται. Εξαιτίας αυτού, ο Mirko αγόρασε ένα χλοοκοπτικό. Για να κουρέψει ολόκληρο το γκαζόν των ~N~ σειρών και στηλών ~M~, πρέπει να περάσει πάνω από κάθε χωράφι τουλάχιστον μία φορά. Μπορεί να ξεκινήσει από οποιοδήποτε πεδίο που βλέπει μία από τις τέσσερις κύριες κατευθύνσεις (πάνω, κάτω, αριστερά και δεξιά). Το χλοοκοπτικό του μπορεί να πάει μόνο προς τα εμπρός (προς το διπλανό χωράφι που βλέπει, προς την κατεύθυνση στην οποία είναι ήδη στραμένο) ή να κάνει μια στροφή 90 μοιρών. Επιπλέον, λόγω της δικής του ασφάλειας, ο Mirko μπορεί να χρησιμοποιήσει μόνο το χλοοκοπτικό στη γη του, άρα δεν μπορεί να φύγει από τον πίνακα.

Δεδομένου ότι η περιστροφή του χλοοκοπτικού δεν είναι απλή, ο Mirko θέλει να κουρέψει το γρασίδι με τις ελάχιστες στροφές. Για κάθε κομμάτι γης που είδε μέχρι στιγμής, ο Mirko θέλει να μάθει τον ελάχιστο αριθμό στροφών που μπορεί να κάνει ώστε να κουρευτεί ολόκληρο το γκαζόν. Βοηθήστε τον Mirko να λύσει αυτό το πρόβλημα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~K\;(1 \le K \le 50\,000)~, τον αριθμό από την εργασία.

Κάθε μία από τις ακόλουθες γραμμές ~K~ περιέχει δύο θετικούς ακέραιους ~N~ και ~M\;(1 \le N, M \le 1\,000\,000)~, τους αριθμούς από την εργασία.

Έξοδος

Για κάθε κομμάτι γης που είδε ο Mirko μέχρι στιγμής, βάλτε σε ξεχωριστή γραμμή τις ελάχιστες στροφές που μπορεί να κάνει, ώστε να κουρευτεί ολόκληρο το γκαζόν.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 50% των συνολικών πόντων, ο Mirko θα δει μόνο ένα κομμάτι γης. Οι διαστάσεις αυτού του κομματιού γης θα είναι μικρότερες από 500.

Παραδείγματα

input

2
1 10
10 1

output

0
0

Επεξήγηση του 1ου παραδείγματος:

Το πρώτο κομμάτι γης μπορεί να κοπεί χωρίς να κάνει στροφές εάν ξεκινήσει από το χωράφι στην πρώτη στήλη του πίνακα, στραμμένο προς τα δεξιά και μόνο προς τα εμπρός. Μια παρόμοια ιδέα ισχύει για το δεύτερο κομμάτι γης.

input

3
1 1
3 3
3 4

output

0
4
4

input

2
5 8
6 4

output

8
6