Doodle

You are doodling on a sheet of grid paper. The doodle starts at the top-left cell (0, 0), and every time a cell is visited an X is written in it.

After writing an X in (0, 0), you move one cell diagonally toward the bottom-right to (1, 1) and write another X. You keep moving along this diagonal, and whenever you reach a border of the paper you flip only the direction (horizontal or vertical) along which you hit it and keep going. If you reach a corner where a horizontal and a vertical border meet, both directions are flipped. You repeat this until you return to the starting cell (0, 0) for the first time.

Given the size of the paper, write a program that computes the number of distinct cells that end up marked with an X.

The first line contains the number of test cases $n$ ($1 \le n \le 4000$).

Each of the following lines contains two natural numbers, the height and the width of the grid paper (in cells), separated by a space. Both values are between $2$ and $20000$, inclusive.

For each test case, print the number of distinct cells marked with an X, one per line.