Мандрівка коня
Коню сумнно бачити одні й ті ж чорні та білі клітинки кожен раз знову і знову, і він вирішив здійснити подорож по усьому світу. Кінь може переміщуватись на дві клітинки у одному напрямку і на одну клітинку у напрямку, перпендикулярному до попереднього. Кінь подорожує по своєму світу усе далі і далі. Наш кінь живе на шаховій дошці, яка має меншу площу, ніж звична дошка 8×8, але все ж є прямокутною. Чи можете ви допомогти цій авантюрній задумці коня здійснити свою подорож?
Для цього вам необхідно знайти такий шлях, на якому кінь відвідує кожну клітинку лише один раз. Шлях коня може починатись і завершуватись у довільній клітинці дошки.
Вхідні дані
Вхідні дані починаються з натурального n у першому рядку. Наступні n рядків містять описи кожного з n тестових випадків. Кожен тест складається з одного рядка, який містить два натуральних числа p та q таких, що 1 ≤ p×q ≤ 26. Цей опис задає шахову дошку розміром p×q, де p описує різні клітинки числами 1, ..., p, а q описує позначення клітинок літерами відповідно. Це перші q літер латинського алфавіту: A, ..., Z .
Вихідні дані
Вихідні дані для кожного тестового випадку розпочинаються з рядка, який містить "Scenario #i:", де i - це номер тестового випадку, починаючи з 1. Далі необхідно вивести один рядок, який містить лексикографічно перший шлях, слідуючи по якому кінь відвідає усі клітинки шахової дошки. Після кожного тестового випадку виводьте порожній рядок. Опис шляху виводьте у одному рядку, послідовно вказуючи імена відвіданих клітинок. Ім'я кожної клітинки складається із великої латинської літери, за якою йде число.
Якщо такого шляху не існує, необхідно вивести у окремому рядку "impossible".