Description
Domo is a brilliant dog. Now he needs to solve these problems to pass the I2P.
In the mid2 practice, Domo has solved the N-Queens M-Rooks Problem, but now, there are some variant problems that need your help to finish.
Note: This problem is separated into three parts, each with different constraints. The differences between each part will be highlighted in red.
The second part of the chess puzzle is N-Knights M-Rooks Problem.
You need to find how many ways to place N knights and M rooks on an (N+M) × (N+M) chessboard such that no two of knight or rook can attack each other in 1 step, and each row and each column contains exactly one knight or one rook.
For N = 2, M = 1, there're 6 solutions:
( 0 means empty spot, R means rook, K means knight. )
R 0 0 0 0 R K 0 0
0 K 0 0 K 0 0 R 0
0 0 K K 0 0 0 0 K
0 0 K K 0 0 0 0 K
0 K 0 0 K 0 0 R 0
R 0 0 0 0 R K 0 0
Note: This is not a valid solution. While none of the two chess can attack each other, we need to ensure that each row and each column contains exactly one chess.
0 R 0 K 0 K 0 0 0
Possible move of Rook:
Possible move of Knight:
Input
The first line consists of an integer T (1 ≤ T ≤ 10) indicating the number of test cases.
For the next T lines, each line consists of two integer N and M (1 ≤ N, M ≤ 9, 1 ≤ N+M ≤ 9)
Output
For each test case, output the number of ways that you can place chesses.