Do đại dịch coronavirus, chính quyền thành phố bắt buộc công dân phải giữ khoảng cách xã hội. Thị trưởng thành phố Semyon muốn thắp sáng công viên Gluharniki để mọi người có thể nhìn thấy nhau ngay cả vào ban đêm để giữ khoảng cách xã hội.

Công viên là một cái bàn hình chữ nhật với n hàng và m cột, trong đó các ô của bảng là hình vuông và ranh giới giữa các ô là các đường đi. Biên giới bên ngoài cũng là đường đi. Đường nào cũng có chiều dài là 1. Ví dụ: công viên với n = m = 2 có 12 đường đi.

Bạn được phân công xây dựng kế hoạch chiếu sáng công viên. Bạn có thể đặt đèn lồng ở giữa đường. Đèn chiếu sáng hai hình vuông gần nó (hoặc chỉ một hình vuông nếu nó đứng trên biên giới của công viên).

Các kích thước công viên là: n = 4, m = 5. Các ô vuông được chiếu sáng được đánh dấu màu vàng. Xin lưu ý rằng tất cả các đường phố có chiều dài 1. Đèn lồng được đặt giữa đường. Trong hình không phải tất cả các ô vuông đều sáng.

Semyon muốn dành ít tiền nhất có thể cho việc thắp sáng nhưng cũng muốn mọi người trên khắp công viên giữ khoảng cách xã hội. Vì vậy, ông yêu cầu bạn tìm số lượng đèn lồng tối thiểu được yêu cầu để thắp sáng tất cả các hình vuông.

Dòng đầu tiên chứa một số nguyên t (1 ≤t≤ 10⁴) - số lượng các trường hợp thử nghiệm trong đầu vào. Sau đó t trường hợp kiểm tra làm theo.

Mỗi trường hợp kiểm tra là một dòng chứa hai số nguyên n, m (1≤n,m≤10⁴) - kích thước công viên.

In t câu trả lời cho các trường hợp kiểm tra. Mỗi câu trả lời phải là một số nguyên duy nhất - số lượng đèn lồng tối thiểu được yêu cầu để thắp sáng tất cả các hình vuông.