Problem C
Doodling

When thinking about a hard problem a lot of people like to doodle, to create “an unfocused drawing that can help the memory and improve abstract thinking”. The most basic form of doodle is a repetitive pattern covering the whole page. One way to create such a pattern is to take a graphing paper and start in the top-left corner $(0,0)$ and fill out the square, then move down and right one square $(1,1)$, fill it out, and so on. Every time you hit the edge of the paper you reverse direction, until you are back at the starting point. This will create a very soothing pattern.

However, to ensure you don’t spend the whole competition doodling you need to figure out how how many squares you will have to fill in the paper to complete the doodle before you even start doodling.

Input

First line of input contains an integer $1 \leq n \leq 4000$, the number of test cases.

Each test case consists of a line containing two integers $2 \leq x\; y \leq 20000$, the height and width (in squares) of the graphing paper.

Output

The number of unique squares you will have filled in before you are done with your doodle.

3
11 3
5 7
5 8

11
12
20