Descripción

Durante las cálidas tardes de primavera, Carlos y Angélica aprovechan el clima soleado para disfrutar su tiempo de ocio al aire libre. Después de pasar horas estudiando programación y algoritmos, deciden darle un descanso a sus mentes y relajarse bajo un árbol florecido jugando al ajedrez. Inspirados por la frescura de la temporada, deciden inventar un nuevo reto basado en un problema clásico.

Casi todo el mundo conoce el dilema de colocar ocho reinas en un tablero de ajedrez de \(8 \times 8\) de manera que ninguna reina pueda capturar a otra. Sin embargo, Carlos y Angélica quieren ir más allá: desean saber el número máximo de piezas de ajedrez de un solo tipo que se pueden colocar en un tablero de dimensiones \(m \times n\) de tal forma que ninguna pieza ataque a otra.

Como es bastante difícil calcular la solución a mano mientras intentan disfrutar de su tarde primaveral, te han pedido ayuda para programar la solución. No necesitan saber la respuesta para todas las piezas del juego. Los peones les parecen bastante aburridos y, de todas formas, Angélica perdió los alfiles entre las flores del jardín. Solo quieren saber cuántas Torres, Caballos, Reinas o Reyes se pueden colocar en el tablero sin que se ataquen entre sí.

Entrada

La primera línea de entrada contiene un entero \(T\), el número de casos de prueba.

Cada caso de prueba consiste en una línea que contiene un carácter del conjunto {r, k, Q, K}, que representan respectivamente las piezas Torre (Rook), Caballo (Knight), Reina (Queen) o Rey (King). El carácter es seguido por los enteros \(m\) \((4 \le m \le 10)\) y \(n\) \((4 \le n \le 10)\), que indican el número de filas y el número de columnas del tablero de ajedrez.

La casilla inferior izquierda es \((1, 1)\).

Salida

Para cada caso de prueba, imprime el número máximo de piezas de ese tipo que se pueden poner en un tablero con las dimensiones dadas, de modo que no estén en posición de atacar a ninguna otra pieza.

Ejemplo

Entrada

2
r 6 7 
k 8 8

Salida

6
32