Lawn Mowing

Time limit1sMemory limit64 MB

Summary

For each N by M grid, find the minimum number of 90-degree turns a lawn mower needs to cover every cell, starting anywhere in any direction.

Level: Medium6 of 10
Topics: Math, Greedy, Implementation, Brute force
Solved: No attempts yet

Problem

Mirko wants to buy land and build a house for his family on it. So far he has seen K plots. Each plot is a rectangle of N rows and M columns, so it has $N \times M$ fields in total.

The plot has to be maintained before construction starts, and the lawn has to be mowed, so Mirko bought a lawn mower. To mow the whole lawn he has to pass over each of the $N \times M$ fields at least once. He can start on any field, facing up, down, left, or right. The mower only moves forward to the adjacent field in the direction it faces, or turns 90 degrees in place. For his own safety Mirko never drives off his land, so the mower stays inside the rectangle.

Turning the mower is hard work, so Mirko wants to mow with as few turns as possible. For each plot, find the smallest number of turns that lets him mow the entire lawn.

Input

The first line contains the integer K ( $1 \le K \le 50000$ ), the number of plots.

Each of the next K lines contains two integers N and M ( $1 \le N, M \le 1000000$ ), the number of rows and the number of columns of one plot, separated by a space.

Output

For each plot, print on its own line the smallest number of turns needed to mow the entire lawn.

Note

A plot with a single row needs no turns. Mirko starts on the field in the first column facing right and drives straight to the end. A plot with a single column works the same way.

Examples3

Example 1
Input
```
2
1 10
10 1
```
Expected output
```
0
0
```
Example 2
Input
```
3
1 1
3 3
3 4
```
Expected output
```
0
4
4
```
Example 3
Input
```
2
5 8
6 4
```
Expected output
```
8
6
```