دیروز تولد هپید و خیکوله بود. دوستان آن‌ها، برای صرفه‌جویی در مخارج تولد، به جای دو کیک تولد، یک کیک تولد مستطیلی تهیه کرده‌اند. اما…

بعد از خواندن ‎»‎تولدت مبارک»، خیکوله نامردی کرد و تمام شمع‌ها را فوت کرد و شمعی به هپید نرسید. هپید که خیلی عصبانی شده بود خیکوله را به دوئل چامپی دعوت کرد و خیکوله هم قبول کرد.

دوئل چامپی یک بازی مهیج (ولی خطرناک) است که دستورالعمل آن در کتاب‌های سیاه المپیادی آمده:

• کیک را ‎$m-1$‎ برش افقی و ‎$n-1$‎ برش عمودی بزنید و قطعات بوجودآمده را به ترتیب شماره‌گذاری کنید. ( قطعه‌ی بالا-چپ ‎$(1‎, ‎1)$‎ و قطعه‌ی پایین-راست ‎$(m‎, ‎n)$‎ خواهد بود)
• حالا روی قطعه‌ی ‎$(1‎, ‎1)$‎ مقدار زیادی سم بریزید.‎
• در هر نوبت، بازیکنی که نوبت اوست یک قطعه مانند ‎$(x‎, ‎y)$‎ را انتخاب می‌کند و باید تمام قطعات $\{(X‎, ‎Y) | X \geq x \wedge Y \geq y\}$‎را بخورد. کسی که آخرین قطعه را بخورد می‌میرد.

پس از مدتی که از شروع دوئل گذشته بود، خیکوله و هپید تازه فهمدند که قطعه‌ی ‎$(1‎, ‎1)$‎ سمّ واقعی است‎!‎ به همین دلیل تصمیم گرفتند از این به بعد بهترین حرکات ممکن را انجام دهند. یعنی اگر بتوانند ببرند حتماً در کوتاه‌ترین زمان (تعداد حرکات) ممکن خواهند برد و اگر محکوم به باخت باشند به نحوی حرکات خود را تنظیم می‌کنند که بیش‌ترین زمان ممکن را زنده بمانند.

طبق تجربه، بهتر است که شما در این دعوا طرف هیچ‌کسی را نگیرید. اما می‌توانید با گرفتن وضعیت کنونی کیک و با توجه به اینکه در حالت کنونی هپید بازی را ادامه می‌دهد، نتیجه‌ی این دوئل را پیش‌بینی کنید‎!‎

• هر تست از چند سناریو تشکیل شده است. در خط اوّل ‎$T$‎ تعداد سناریوها می‌آید. هر سناریو به صورت زیر توصیف می‌شود:‎
  • در ابتدا دو عدد ‎$n$‎ و ‎$m$‎ می‌آید که نشان‌دهنده‌ی اندازه‌ی کیک است.‎
  • به دنبال آن، وضعیت کیک می‌آید. ‎'!'‎ نشان‌دهنده‌ی قطعه‌ی سمی، ‎'C'‎ نشان‌دهنده‌ی کیک دست‌نخورده و '.'‎ نشان‌دهنده‌ی قطعه‌ی خورده‌شده از کیک است. (به تست نمونه مراجعه کنید)
• تمام سناریوها معتبر هستند. (یعنی حاصل دوئل هپید و خیکوله روی یک کیکِ دست‌نخورده‌ی ‎$m \times n$‎‎ هستند) برای مثال قطعاً اوّلین کاراکتر '!'‎ خواهد بود.
• ‎در ‎۳۰٪‎ تست‌ها: ‎$n‎ + ‎m \leq 9$‎ و ‎$T \leq 5$‎
• ‎در ‎۱۰٪‎ تست‌ها محدودیت زمانی به ‎$0.1$‎ ثانیه کاهش یافته. این دسته با دسته‌ی قبل اشتراکی ندارد.
• ‎در تمام تست‌ها: ‎$1 \leq m‎, ‎n \leq 8$‎ و ‎$1 \leq T \leq 50$‎

به ازای هر سناریو، در خروجی حرف اول اسم بازنده ‎H)‎ برای هپید، و ‎K‎ برای خیکوله) و سپس مدت زمانی که زنده می‌ماند را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال قبل

‎