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

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

Входные данные

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

Размеры доски не превышают 10, т.е. 4 <= M <= 10 и 4 <= N <= 10.

Выходные данные

Для каждого тестового случая вывести в отдельной строке ответ для заданной фигуры и указанных размеров доски.