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 first part of the chess puzzle is N-Queens M-Rooks Problem.
You need to find how many ways to place N queens and M rooks on an (N+M) × (N+M) chessboard such that no two of queens or rooks can attack each other in 1 step.
For N = 1, M = 2, there're 4 solutions:
( 0 means empty spot, Q means queen, R means rook. )
Q 0 0 0 R 0
0 0 R R 0 0
0 R 0 0 0 Q
0 R 0 0 0 Q
0 0 R R 0 0
Q 0 0 0 R 0
Possible move of Queen:
Possible move of Rook:
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.