A Game With a Sheet of Paper

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Yuuko and Nagi like to play the following game:
Initially they take a checkered sheet of paper of the size of N x M cells. Then, one cell, let's call this cell (X, Y) is marked. Then, they take the moves alternately. A move consists of making a long horizontal or vertical cut. This cut should coincide with one of the lines that divide the sheet into cells. Then, a part that doesn't contain a marked cell is thrown away and another player takes her turn. A player who is unable to make a turn because after the opponent's turn the dimensions of the sheet became equal to 1 x 1 loses. Yuuko plays first.
Yuuko and Nagi have played a lot of games together so now they both know the optimal strategy and always use it. Today girls are going to play a game on a N x M cells sheet of paper, but they haven't yet decided, what is the cell (X, Y) to be marked. Yuuko is interested, in how many ways it's possible to choose this cell so the she can become a winner, regardless of Nagi's moves.
Input
The first line of input consists of an integer T  the number of test cases. Then, T lines describing the test cases follow. The ith such line contains two integers N and M, separated by a single space.
Output
For each test case, output a single line containing the number of ways to choose the marked cell in order to ensure Yuuko's win.
Example
Input: 2 5 8 6 7 Output: 40 42
Scoring
T = 100, 1 <= N, M <= 10 : 25 points.
T = 100, 1 <= N, M <= 1000 : 36 points.
T = 100, 1 <= N, M <= 10^{6} : 39 points.
Author:  xcwgf666 
Tester:  
Editorial  http://discuss.codechef.com/problems/SHGAME 
Tags  easy, ltime10, nim, xcwgf666 
Date Added:  8032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 