Game of chess

All submissions for this problem are available.
Background
A chess game is currently running between Viswanathan Anand & Garry Kasparov. Anand is very few moves away from his victory & Garry’s condition is really bad. Garry is thinking about a knight (the horsehead piece) moves quite differently than any other piece. Help Garry to make the move at any condition. Knight moves in an Ltype shape. That is, it can move two squares in one direction, then one square in the perpendicular direction (knights can not move diagonally). As an example, consider this:
. . . . . . . .
. . . . . . . .
. . . * . * . .
. . * . . . * .
. . . . K . . .
. . * . . . * .
. . . * . * . .
. . . . . . . .
The knight is in the square marked by a `K'. The `*' around it are the possible positions the knight can move on the next turn. The `.' are empty squares.
If they have two knights on the board, things get a little more complicated. We say that a knight can not be taken if there is not knight that can land on it's square on the next turn. This condition has to hold regardless of what order the knights move (ie, the knights can't `move' out of the way).
Input:
First line of input T represents the number of test cases.
Next line of input will have two integers, M, N, separated by exactly one space. The chessboard has size M x M. We're interested in placing N knights on the board such that no knight can take any other knight. The number of knights will be in the range 1 to 36 (inclusive). M will be in the range 1 to 6 (inclusive).
Output:
For each line of input, your program should print out the number of ways that we can place N knights on an M x M chessboard. The answer will always fit in an unsigned, 32 bit integer.
Sample Input
4 2 2 3 2 6 4 6 15
Sample Output
6 28 26133 2560
Author:  opengeest 
Tags  opengeest 
Date Added:  14022013 
Time Limit:  0.642 sec 
Source Limit:  5000 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. 