Mirko wants to buy land on which he will build a house for his family. So far, he's seen
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
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 input contains the positive integer
Each of the following
Output Specification
For each piece of land Mirko saw so far, output in a separate line the minimal amount of turns he can take so that the entire lawn is mowed.
Scoring
In test cases worth 50% of total points, Mirko will see only one piece of land. The dimensions of this piece of land will be smaller than 500.
Sample Input 1
2
1 10
10 1
Sample Output 1
0
0
Explanation for Sample Output 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.
Sample Input 2
3
1 1
3 3
3 4
Sample Output 2
0
4
4
Sample Input 3
2
5 8
6 4
Sample Output 3
8
6
Comments