Maximum quantity of figures#311
Almost everyone knows the problem of placing eight queens on an 8 \times 8 chessboard so that no queen attacks another. Your task is to determine the maximum number of pieces of a single type that can be placed on an M \times N board so that no piece attacks any other.
However, you should consider only certain pieces. Pawns are excluded from consideration, and bishops are also not included. Therefore, you need to determine how many rooks, knights, queens, or kings can be placed on a board so that none attack each other.
The first line contains the number of problems . Each of the following lines describes a problem. Each line starts with a character from the set , , , or representing a rook, knight, queen, or king, followed by two integers and (4 \leq M \leq 10, 4 \leq N \leq 10) — the number of rows and columns of the board.
For each problem, output a single line with the maximum number of pieces that can be placed on a board of the given type and size so that none attack each other.
Example 1