Masala B

Muhammadamin naqsh chizishga juda qiziqadi. Bu qiziqish unda endi qo'liga ruchka olishni boshlagan davrlardan bor, u o'shanda uydagi hamma devorlarga "chiroyli" qilib "naqsh"lar chizib chiqgan.

Hozir u katta bo'lgan. Shu sababli u endi devorlarga emas, millimetr qog'oziga naqshlar chizadi.

Faqatgina oq yoki qora kvadratchalardan iborat \(N \times M\) o'lchamli naqshda agarda hech bir qatorida, hamda, hech bir ustunida ketma-ket 3 ta bir xil rangli kvadratcha uchramasa bunday naqshni Muhammadamin chiroyli deb hisoblaydi, va bu naqshning chiroylilik darajasi undagi qora kvadratchalar soniga teng deb hisoblaydi.

Ayni vaqtda Muhammadaminda o'lchami \(A \times B\) millimetr qog'ozi bor. Muhammadamin bu qog'ozga naqsh chizmoqchi. Unga chizishi mumkin bo'lgan naqshning chiroylilik darajasi maksimal nechchi bo'lishini aniqlashda yordam bering.

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10^5)\) - testlar soni kiritiladi.

Keyingi \(T\) ta qatorning har birida ikkitadan butun son, \(A(1 \le A \le 10^9)\) va \(B(1 \le B \le 10^9)\) sonlari kiritiladi.

Har bir test uchun alohida qatorda bitta butun son, o'lchami \(A \times B\) bo'lgan naqshning maksimal chiroylilik darajasini chop eting.