Nguồn: https://www.codechef.com
Leha đang chơi một trò vô cùng thú
vị. Trò chơi được chơi trên một lưới hình chữ nhật gồm N hàng và M cột. Ban đầu
tất cả các ô trong lưới đều chưa được tô màu.
Số điểm ban đầu của Leha là 0. Với
mỗi lượt chơi, anh ta chọn một ô chưa được tô màu, và tô màu nó. Điểm số của
một bước là số ô láng giềng đã được tô màu của ô Leha tô trong bước đó. Hai ô
gọi là láng giềng nếu có chung cạnh. Trò chơi sẽ kết thúc nếu tất cả các ô đều
được tô màu. Kết thúc, điểm số chung cuộc là tổng số điểm mỗi lượt.
Leha muốn biết điểm số cao nhất anh ta có thể đạt được. Bạn
có thể giúp anh ta tìm ra nó không?
Dữ liệu vào:
· Dòng đầu tiên của input chứa một số tự nhiên T – số lượng test.
· T dòng tiếp theo, mỗi dòng chứa hai số nguyên N và M là thích thước của lưới.
Dữ liệu ra:
· Với mỗi test, in ra một dòng chứa một số nguyên tương ứng
với số điểm lớn nhất Leha có thể đạt được.
Ràng buộc:
· 1 ≤ T ≤ 100
· 1 ≤ N, M ≤ 1 000
Subtask:
· Subtask #1[30
điểm]: 1 ≤ N, M ≤ 3
· Subtask #2[70
điểm]: 1 ≤ N, M ≤ 1 000
Ví dụ:
Input
1
2 2
Output:
4
Leha có thể đạt số điểm chung cuộc là 4 theo cách sau.
· Ban đầu, anh ta tô màu ô trái dưới, tất cả các ô láng giềng
đều chưa được tô màu nên được cộng 0 điểm.
· Bước hai, anh ta tô màu ô phải trên và cũng được 0 điểm.
· Bước ba anh ta tô màu ô trái trên. Ô này có hai láng giềng
và đều đã được tô màu nên sẽ được cộng 2 điểm.
·
Bước cuối, anh ta chọn ô phải dưới.
Ô này có hai láng giềng và đều đã được tô màu nên sẽ được cộng 2 điểm.
Leha không thể đạt số điểm nhiều hơn 4. Do đó 4 là đáp án.
