Minimal Turns for Lawn Mowing

Mirko wants to buy a piece of land to build a house and needs to mow the entire lawn using his lawn mower. The lawn is presented as a rectangular matrix with N rows and M columns. Mirko can start from any cell facing one of the four main directions (up, down, left, or right). The mower can only move forward (to the adjacent cell in the same direction) or make a 90° turn. However, it is not allowed to leave the boundaries of the matrix.

Mirko's goal is to cover every cell (field) at least once while minimizing the number of turns (a turn is a change in direction by 90°). For each plot of land, you are to compute the minimal number of turns required in order to mow the entire lawn.

Important Observations:

• If either N or M is 1, the mower can cover the entire lawn in a straight line with no turns.
• If both N and M are greater than 1, an optimal snake-like path can be used. In fact, the minimal number of turns is given by \[ T = 2\times(\min(N, M) - 1), \] where \(T\) is the minimal number of turns.

Use the above logic to determine the minimal number of turns for each piece of land.

inputFormat

The input begins with an integer K (1 ≤ K ≤ 10⁴) representing the number of test cases. Each test case consists of a single line containing two integers N and M (1 ≤ N, M ≤ 10⁹), denoting the number of rows and columns of the land, respectively.

outputFormat

For each test case, output a single line with the minimal number of 90° turns required to cover every cell of the lawn at least once.

sample

3
1 5
2 2
3 3

0
2
4