Досить відома задача про розміщення 8-ми ферзів на звичайній шаховій дошці розміром 8 х 8 таким чином, щоб жоден з ферзів не знаходився під боєм довільного іншого. Матроскін хоче знати, яку максимальну кількість фігур одного виду можна поставити на дошці M х N таким чином, щоб жодна з фігур не знаходилась під боєм довільної іншої. Для нього це завдання виявилось чомусь складним і він просить вас допомогти йому вирішити цю проблему.

Причому його цікавлять не всі випадки. Пішаки йому здаються чомусь досить не цікавими, крім того з невідомої причини він любить слонів. Тому він хоче лише знати, скільки тур, коней, ферзів або королів, можуть бути розміщені на одній дошці таким чином.

Вхідні дані

Перший рядок вхідних даних містить кількість завдань у тесті T. Далі йде T рядків, які містять нове завдання. Кожне завдання розміщено у новому рядку і розпочинається з одного символу (назви фігури) з наступного набору R, N, Q та K, які позначають, відповідно, туру, коня, ферзя або короля, далі через пропуск задано розміри дошки.

Розміри дошки не перевищують 10, тобто 4 <= M <= 10 та 4 <= N <= 10.

Вихідні дані

Для кожного тестового випадку вивести в окремому рядку відповідь для заданої фігури та вказаних розмірів дошки.