Широко известна задача о расстановке 8-ми ферзей на обычной шахматной доске размером 8 х 8 таким образом, чтобы ни один из ферзей не находился под боем любого другого. Матроскин хочет знать, какое максимальное количество фигур одного вида можно поставить на доске M
х N
таким образом, чтобы ни одна из фигур не находилась под боем любой другой. Для него эта задача оказалась почему-то сложной и он просит вас помочь ему решить эту проблему.
Причем его интересуют не все случаи. Пешки ему кажутся почему-то довольно неинтересными, да и он по неизвестной причине не любит слонов. Поэтому он хочет только знать, сколько ладей, коней, ферзей или королей, могут быть размещены на одной доске таким образом.
Первая строка ввода содержит количество заданий в тесте T
. Далее следует T
строк, содержащих новое задание. Каждое задание описано в новой строке и начинается из одного символа (названия фигуры) из следующего набора R
, N
, Q
и K
, которые обозначают, соответственно, ладью, коня, ферзя или короля, далее через пробел заданы размеры доски.
Размеры доски не превышают 10, т.е. 4 <= M <= 10
и 4 <= N <= 10
.
Для каждого тестового случая вывести в отдельной строке ответ для заданной фигуры и указанных размеров доски.