Bạn được cho một bảng hình chữ nhật gồm \(M \times N\) ô vuông.

Bạn có vô vàn những khúc domino có kích thước \(2 \times 1\). Bạn có quyền xoay hướng của domino nếu cần.

Nhiệm vụ của bạn là tìm số lượng nhiều nhất các cục domino sao cho:

• Cứ \(2\) cục domino thì phủ hết \(1\) hình vuông.

• Không có 2 cục domino nào chồng lên nhau.

• Các cục domino phải nằm gọn bên trong bảng hình chữ nhật trên. Các cục domino được phép chạm cạnh của hình vuông.

Ps1: Các domino không nhất thiết phải phủ lắp hết toàn bộ hình chữ nhật !

Ps2: Bài tập này chỉ có \(1\) testcase duy nhất, bao gồm \(400\) câu hỏi.

Input

• Một dòng duy nhất gồm \(2\) số nguyên dương \(M\) và \(N\) \((1 \le M \le N \le 2021110720211107)\)

Output

• Ứng với mỗi câu hỏi, in ra đáp cần tìm.

Example

2 4

4