C — The Lawn Mower

Mirko wants to buy some land on which he will build a house for his family. So far, he's seen K pieces of land. Each of them is in the shape of a rectangle, and we can think of it as a matrix with N rows and M columns, N × M fields in total.

Mirko is aware that, before construction begins, the property needs to be regularly maintained, and the lawn needs to be mowed. Because of this, Mirko bought a lawn mower. In order to mow the entire lawn of N rows and M columns, he needs to go over each field at least once. He can start from any field facing one of the four main directions (up, down, left, and right). His lawn mower can only go forwards (to the adjacent field facing the current direction) or make a 90-degree turn. Additionally, because of his own safety, Mirko can only use the lawn mower on his land, so he cannot leave the matrix.

Since making the lawn mower turn isn't simple, Mirko wants to mow the lawn with the minimal amount of turns. For each piece of land he saw so far, Mirko wants to know the minimal number of turns he can make so that the entire lawn is mowed. Help Mirko solve this problem.

Input Specification

The first line of the input contains a positive integer K (1 ≤ K ≤ 50 000), the number of pieces of land Mirko has seen so far.

Each of the following K lines contains two positive integers N and M (1 ≤ N, M ≤ 1 000 000), the number of rows and the number of columns of the land, respectively.

Output Specification

For each piece of land Mirko has seen so far, output in a separate line the minimal amount of turns he can make so that the entire lawn is mowed.

Sample Input 1

1. 2
2. 1 10
3. 10 1

download as text file

Output for Sample Input 1

1. 0
2. 0

download as text file

Sample Input 2

1. 3
2. 1 1
3. 3 3
4. 3 4

download as text file

Output for Sample Input 2

1. 0
2. 4
3. 4

download as text file

Sample Input 3

1. 2
2. 5 8
3. 6 4

download as text file

Output for Sample Input 3

1. 8
2. 6

download as text file

Clarification of Sample 1

The first piece of land can be mowed without making any turns if he starts from the field in the first column of the table, faced to the right, and only going forwards. A similar idea applies for the second piece of land.

Original Problem

Croatian Open Competition in Informatics 2017/2018, Contest #2, Kosnja