Decorating Cake

Bạn được cho 1 chiếc bánh hình chữ nhật gồm m x n miếng bánh nhỏ. Bạn muốn trang trí cho bánh bằng cách dùng máy xịt kem qua tất cả các miếng bánh. Bạn có thể bắt đầu từ 1 miếng bánh bất kỳ, hướng máy xịt theo 1 trong 4 hướng trên, dưới, trái, phải và xịt kem về phía trước hoặc quay 90° (quẹo trái hoặc phải). Bạn chỉ được xịt kem trong phạm vi chiếc bánh.
Bạn hãy tính số lần tối thiểu mà máy xịt kem phải quay 90° để có thể đi qua tất cả miếng bánh.

Ví dụ: 

• Với m = 2, n = 3 thì đáp án là 2.
• Giải thích:
• Xuất phát từ ô (1,1) và quay phải (90°) 2 lần.
• Trong bài này bạn sẽ được cho T test mỗi test sẽ có dạng (mi, ni). 

[Đầu vào/ Đầu ra]:

• [Giới hạn thời gian]: 0.5s với C++,3s với Java & C#,4s với Python,Go,Js.
• [Đầu vào]: Mảng T gồm các cặp số mi, ni. (1 ≤ |T| ≤ 105) (1 ≤ mi, ni ≤ 1018).
• [Đầu ra]: Gồm |T| số tương ứng với đáp án của test thứ i.