Có một quân mã trên bàn cờ vô hạn. Các hàng và cột được đánh số bắt đầu từ \(1\).

Nhiệm vụ của bạn là xử lý hiệu quả các truy vấn dạng: khi quân mã bắt đầu tại vị trí \((x,y)\), số nước đi tối thiểu mà quân mã cần thực hiện để đến góc trên bên trái là bao nhiêu.

Đầu vào

Dòng đầu tiên chứa một số nguyên \(n\): số lượng truy vấn.

Sau đó có \(n\) dòng. Mỗi dòng chứa hai số nguyên \(x\) và \(y\): vị trí của quân mã.

Đầu ra

Với mỗi truy vấn, in số nước đi tối thiểu.

Constraints

• \(1 \le n \le 10^5\)

• \(1 \le x, y \le 10^9\)

Example

4
1 1
2 3
4 1
42 1337

0
1
3
669