Yum Yum

Do only humans have dreams? If so, the story below may seem impossible to you…

A flat frog dreamed that it was sitting in one corner of a flat rectangular room measuring $n$ by $m$ units. In its dream the room was full of — yum yum — tasty flies. The flies sat at every point of the room with integer coordinates, except the point where the frog was standing. Yum yum. So in total there were $(n + 1)(m + 1) - 1$ delicious flies. The dream did not last long. When the frog woke up, it began to wonder how much effort it would take to eat all the flies. Yum yum.

The frog has a tongue that, as every child knows, is very long (it reaches every fly in the room) and can be shot out in a straight line. When the frog shoots its tongue in a given direction, every fly — yum yum — that lies on its path sticks to it and is eaten. Oh, yum yum. Help the frog: what is the minimum number of times it must shoot out its tongue to eat all the flies? You may assume that flies are points and the tongue is infinitely thin.

The first line contains a natural number $d$ ($1 \le d \le 100$), the number of test cases; their descriptions follow on the next lines.

Each test consists of a line with two integers $n$, $m$ ($0 \le n, m \le 10^6$).

For each test, print a line containing the minimum number of tongue shots the frog needs in order to eat all the flies (yum yum) in the room.