Sau một ngày đi tuần vất vả trên cái bàn cờ vua kích thước ~n \times n~, cũng đã đến lúc quân Mã được nghỉ ngơi. Biết rằng hiện tại quân Mã đang đứng ở ô có tọa độ (m, n), hãy chỉ ra số bước nhảy ít nhất để di chuyển quân Mã đó về nhà ở ô (1, 1).

Đề bài có q truy vấn, mỗi truy vấn gồm tọa độ (m, n). Để được toàn bộ số điểm của 1 test bạn cần trả lời đúng q truy vấn này.

Input:

• Dòng đầu tiên chứa 2 số nguyên ~n, q~ ~(1 <= n <= 1000)~
• ~q~ dòng tiếp theo mỗi dòng chứa 2 số nguyên ~x_i, y_i~

Output:

• In ra ~q~ dòng, dòng thứ ~i~ là số bước nhảy ít nhất để di chuyển từ ô ~(x_i, y_i)~ về ô ~(1, 1)~. Trong trường hợp không đi được thì in ra -1

Sample Input 1

3 4
1 3
1 1
2 1
2 2

Sample Output 1

2
0
3
-1

Sample Input 2

4 4
4 4
4 1
3 3
1 1

Sample Output 2

2
5
4
0