Two Snakes In A Grid

All submissions for this problem are available.
Given an rectangular grid of N rows and M columns, each cell can be labeled black (Yin) or white (Yang). Two cells are neighbors if they share a common unitlength edge segment. The grid is valid if all the black cells form a path, and all the white cells form a path. A path is a set S of cells defined as follows:
The cells form a connected piece. From each cell in S, you can reach any other cell in S by moving between neighbors within S. Exactly two cells in S have exactly one neighbor in S each. These are the "ends" of the path. Every other cell in S has exactly two neighbors in S.
Given N and M, compute the number of valid grids. Note that symmetry doesn't matter  as long as two valid grids differ in one position they are considered different, even if one can be rotated or flipped to the other.
Input
The first line of the input will be a single integer T, the number of test cases. T lines follow, each of which contains two integers separated by a space: "N M", as defined above.
Output
For each test case, output the number of valid grids of the specified size..
Example
Input: 3 4 4 4 6 5 5 Output: 24 44 48
Author:  codecheftsec 
Tags  codecheftsec 
Date Added:  18022013 
Time Limit:  0.72 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. 