文理学院程序设计在线练习


Kira Yoshikage’s Chessboard

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

In order to enjoy a peaceful life, Kira Yoshikage bought a new chessboard with the size of n x m. He wants to know how many Knights (A kind of piece in chess) he can put on the chessboard, that there is at least one cell is ‘free’. A cell called ‘free’ means that there is no knight on the cell and the cell can’t be reached by any knight in one move.

Input

The first line of data is the number of cases T.
The only line of each test case contains two integers n and m which represent the size of the chessboard.
1 ≤ T ≤ 1000
1 ≤ n, m ≤ 100

Output

For each test case print one integer – the maximum number of Knights can be put on the chessboard.

Sample Input
2
1 1
1 2
Sample Output
0
1
Hint


The definition of knight: A knight moves to any of the closest squares that are not on the same rank, file, or diagonal. (Thus the move forms an "L"-shape: two squares vertically and one square horizontally, or two squares horizontally and one square vertically.) The knight is the only piece that can leap over other pieces.

Source

2019绍兴市计算机技能竞赛