Luis is a great chess player and as such, he likes to test any kind of game that he imagines with the chess pieces, he just created a game pretty interesting consisting in the moves of a knight over all the possible cell whenever he can in a matrix sized board WxH, being in the position (x,y) of the matrix, the knight can move to (x+2,y+1), (x+1,y+2), (x-2,y+1), (x+2,y-1), (x-1,y+2), (x-1,y-2), (x-2,y-1), (x+1,y-2).

The knight can start from any cell in the matrix WxH, the knight may never leave the matrix and it can step an arbitrarily number of times the same cell visited, however, you shouldn't count the repeated step.

Input details:

T as an integer representing the number of cases, then, in the next T lines, two integers W and H representing the width and the height of the matrix.

Output details:

A single number representing the number of cells visited by the knight in the matrix.

Constraints:

1 <= W <= 100,000

1 <= H <= 100,000