V_AYP1_B - Knight Circuit

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.

 

 

INPUT

OUTPUT

3

1 1

15 2

100 100

1

8

10000

 

Constraints:

1 <= W <= 100,000

1 <= H <= 100,000

 


Added by:Venezuelan Programming League
Date:2013-02-02
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.