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