Lawn Mowing

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.

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.

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

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.