Given a m × n chess board, determine the minimum number of places to be covered to make it impossible to put a L shaped trinomo on it.

e.g. In 2 × 2 chess board if you cover any 2 cells, it will be impossible to put a L shaped trinomo on it.

1 <= n, m <= 10^8

A trinomo is a L shaped object.

*
* *

where * represents a cell.

Input

T: number of test cases (T <= 5000)

Next T lines:

every line contain m, n

Output

Minimum number of cells to be covered.

Example

Input:
1
2 2

Output:
2