Maksimal fiqur sayı
8x8 ölçülü şahmat taxtasında 8 vəzir yerləşdirmək məsələsi kifayət qədər məşhurdur. Bu vəzirlər elə yerləşdirilməlidir ki, heç biri digərinin zərbə məsafəsində olmasın. Matroskin bilmək istəyir ki, M x N ölçülü taxtada bir növ fiqurun maksimum neçə ədədini elə yerləşdirmək olar ki, heç biri digərinin zərbə məsafəsində olmasın. Bu məsələ onun üçün nədənsə çətin olub və sizdən bu problemi həll etməyə kömək etməyinizi xahiş edir.
Bununla belə, o, bütün hallarla maraqlanmır. Piyada fiqurları ona nədənsə maraqsız gəlir, həmçinin naməlum səbəbdən o, filləri sevir. Buna görə də o, yalnız qalan, atlar, vəzirlər və ya şahların bir taxtada necə yerləşdirilə biləcəyini bilmək istəyir.
Giriş məlumatları
Giriş məlumatlarının ilk sətiri testdəki tapşırıqların sayını T ehtiva edir. Sonra T sətir gəlir, hər biri yeni bir tapşırıq ehtiva edir. Hər bir tapşırıq yeni sətirdə yerləşdirilir və R, N, Q və K dəstindən olan bir simvolla (fiqurun adı) başlayır, bu da müvafiq olaraq qalan, at, vəzir və ya şahı göstərir, sonra boşluqla taxtanın ölçüləri verilir.
Taxtanın ölçüləri 10-dan çox deyil, yəni 4 <= M <= 10 və 4 <= N <= 10.
Çıxış məlumatları
Hər bir test halı üçün verilmiş fiqur və göstərilən taxta ölçüləri üçün cavabı ayrıca sətirdə çıxarın.