+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ترب و تربچه مشغول بازی کردن شطرنج هستند. بازی شطرنج آن‌ها روی یک جدول $n \times n$ انجام می‌شود. ترب با رنگ سفید و تربچه با رنگ سیاه بازی می‌کند. ترب سه مهره دارد، دو مهره‌ی رخ و یک مهره‌ی شاه دارد. تربچه یک مهره‌ی شاه دارد. اکنون وضعیت اولیه بازی با ۴ مهره به شما داده می‌شود. فرض کنید ترب به هوشمندانه ترین شکل ممکن بازی می‌کنند ولی تربچه که فقط یک مهره‌ی شاه دارد هر بار از بالاترین سطر شروع می‌کند و به ترتیب از چپ به راست به اولین خانه‌ای که بتواند حرکت کند، حرکتش را انجام می‌دهد. (ترتیب خانه‌ها عبارت است از بالا چپ، بالا، بالا راست، چپ، راست، پایین چپ، پایین و پایین راست) حال از شما می‌خواهیم کمترین تعداد حرکت لازم برای پایان بازی را چاپ کنید. ## قوانین بازی شطرنج مهره‌ی شاه در یک حرکت می‌تواند به یک خانه‌ی مجاور راسی برود که هیچ کدام از مهره‌های همرنگ خودش در آن نیست (اگر به خانه‌ای برود که مهره‌ی غیرهمرنگ باشد و آن مهره شاه نباشد، آن مهره را از صفحه بازی حذف می‌کند و به‌جای آن قرار می‌گیرد). مهره‌ی شاه نمی‌تواند به خانه‌ای برود که ممکن است در حرکت بعدی حریف، باعث حذف شدن شاه شود (همان مفهوم «کیش شدن»). مهره‌ی رخ می‌تواند به همه‌ی خانه‌های هم سطر و یا هم ستونش که هیچ مهره‌ای در بازه‌ی بین آن‌ها نیست، حرکت کند (نمی‌تواند از روی دیگر مهره‌ها بپرد). اگر در یک وضعیت مهره‌ی شاه بازیکنی مورد تهدید یک بازیکن دیگر باشد، باید در حرکت بعدی، خودش را از آن وضعیت خارج کند و نمی‌تواند کار دیگری انجام دهد. بازی به نوبت انجام می‌شود، ابتدای بازی نوبت مهره‌های سفید است و سپس سیاه و بعد از آن به نوبت و یک حرکت انجام می‌دهند. اگر بازیکنی نتواند در نوبت خودش حرکت انجام دهد بازی تمام می‌شود. اگر وضعیت طوری باشد که شاه در معرض تهدید باشد، تهدید کننده برنده‌ی بازی است ولی اگر شاه هیچ تهدیدی نشده باشد ولی هیچ مهره‌ای را نمی‌توان حرکت داد، بازی مساوی می‌شود. اگر هیچ بازیکنی هیچ راه‌ پیروزی نداشته باشد بازی به تساوی منجر می‌شود. # ورودی در سطر اول ورودی عدد صحیح و مثبت $n$ آمده که ابعاد صفحه‌ی شطرنج را نشان می‌دهد. $$3 \leq n \leq 4$$ در سطر دوم ورودی عدد صحیح و مثبت $t$ آمده که تعداد سناریوهای مختلف را نشان می‌دهد. $$1 \leq t \leq 10\,000$$ در هر سناریو یک جدول $n \times n$ از کاراکترها بدون فاصله داده می‌شود. در واقع هر جدول $n$ رشته به طول $n$ است که کاراکترهای آن `K` و `R` و `.` و `k` است که به ترتیب مهره‌ی شاه سفید، رخ سفید، خانه خالی و شاه سیاه را نشان می‌دهد. تضمین می‌شود در جدول داده شده مهره‌ی شاه سیاه در معرض تهدید نباشد، دو مهره‌ی رخ سفید و یک شاه سفید و یک شاه سیاه در جدول باشد و بقیه‌ی خانه‌ها خالی باشند. تضمین می‌شود در وضعیت اولیه، شاه کسی در معرض تهدید نیست و فرض کنید بعد از این وضعیت نوبت رنگ سفید است. # محدودیت‌ها | زیرمسئله |‌ محدودیت‌ها | امتیاز | |:---:|:---:|:---:| | ۱ | $n = 3$ | ۵۰ | | ۲ | بدون محدودیت اضافه | ۵۰ | # خروجی خروجی $t$ سطر دارد، در هر سطر با فرض اینکه هر دو بازیکن بهترین بازی خود را ارائه دهند، کمترین تعداد حرکت برای پیروزی را با `CheckMate` و سپس تعداد مراحل را چاپ کنید و یا عدم امکان پیروزی و همان تساوی یا `Draw` را چاپ کنید (به نمونه خروجی توجه کنید). # مثال ## ورودی نمونه ۱ ``` 4 2 .R.K ..R. .... k... ...K ..R. .k.. R... ``` ## خروجی نمونه ۱ ``` CheckMate 1 CheckMate 5 ``` <details class="blue"> <summary> توضیح نمونه ۱ </summary> توضیح وضعیت اول ``` .R.K R... .... k... ``` توضیح وضعیت دوم: ``` ...K .... .k.. R.R. ...K .k.. .... R.R. .... .k.K .... R.R. .k.. ...K .... R.R. .k.. ...K .... RR.. ``` </details>

حل سؤال در بانک سؤالات