Doodle

Time limit1sMemory limit128 MB

Summary

A diagonal walk bounces off the rectangle's borders and corners; count how many distinct cells it marks before returning to the start.

Level: Medium7 of 10
Topics: Math, Number theory, Simulation, Implementation
Solved: No attempts yet

Statement

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.

Input

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.

Output

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

Examples1

Example 1
Input
```
3
11 3
5 7
5 8
```
Expected output
```
11
12
20
```