eolymp
bolt
Try our new interface for solving problems
Problems

Maximum quantity of figures

Maximum quantity of figures

Time limit 0.1 seconds
Memory limit 64 MiB
prb311

Almost everyone knows the problem of putting eight queens on an 8 х 8 chessboard such that no Queen can take another Queen. Matroskin wants to know the maximum number of chesspieces of one kind which can be put on an m x n board with a certain size such that no piece can take another. Because it's rather difficult to find a solution by hand, he asks your help to solve the problem.

He doesn't need to know the answer for every piece. Pawns seems rather uninteresting and he doesn't like Bishops anyway. He only wants to know how many Rooks, kNights, Queens or Kings can be placed on one board, such that one piece can't take any other.

Input data

The first line of input contains the number of problems. A problem is stated on one line and consists of one character from the following set R, N, Q, K, meaning respectively the chesspieces Rook, kNight, Queen or King. The character is followed by the integers m (4 <= m <= 10) and n (4 <= n <= 10), meaning the number of rows and the number of columns or the board.

Output data

For each problem specification in the input your program should output the maximum number of chesspieces which can be put on a board with the given formats so they are not in position to take any other piece.

Examples

Input example #1
2
R 6 7
N 8 8
Output example #1
6
32