A simple Knight's problem How many ways are there to place a black and a white knight on an N * M chessboard such that they do not attack each other? 

A knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally.

The knights have to be placed on different squares and the knights attack each other if one can reach the other in one move.

Input:

The first line contains the number of test cases T. Each of the next T lines contains two integers N and M, representing the dimensions of the board.

Output:

Output T lines, one for each test case, each containing the required answer for the corresponding test case.

Sample input:

3
2 2
2 3
4 5


Sample output:

12
26
312


Constraints

    1 &lt;= T &lt;= 10000
    1 &lt;= N,M &lt;= 100000
time limit 1 sec


Source Limit:   

50000 Bytes


Winning criteria

Shortest code which runs with specified time limit decides the winner


i ll leave two days time for more users to try from today
GNU Octave, 55 56 58 78 87* 93 chars

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g


Octave doesn't take input from STDIN, so you've got to provide the input in the program:

t = [
    1 7;
    2 2;
    2 3;
    4 5;
    5000 6000 
];                % test cases

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g


The logic is as follows:

nchoosek(n*m, 2) gives us the number of combinations of two positions we can have on a N*M board. We then multiply it by two since we have two different knights.

Then we work out how many 3*2 blocks fit in an N*M board. For each 3*2 block there are 4 different positions our knights can be attacking each other. So we multiply it by 4 and subtract it from the value we calculated above.

*thanks to a simplification of the nchoosek I shamelessly stole from Matt.

Edit

I've just tested this on my laptop to make sure it meets the time requirements.

It will compute 500,000 10,000,000 test cases in an average of 0.918787 0.231201 seconds