What is the maximum number of soldiers (chess) that can be placed in a m × n board so that none of them attack each other?

Input

The first line is an integer t, denoting the number of test cases. Each test case is a single line with two integers m and n the number of rows and columns in the board.

Output

For each test case print the maximum number of soldiers that can be placed in a separate line.

Constraints

1 ≤ t ≤ 100

1 ≤ m ≤ 10³⁰

1 ≤ n ≤ 10³⁰

Example

Input:
4
10 10
3 3
5 5
3 6

Output:
50
6
15
12