Путешествие коня
Коню скучно видеть одни и те же черные и белые клетки каждый раз снова и снова, и он решил совершить путешествие по всему миру. Конь может перемещаться на две клетки в одном направлении и на одну клетку в направлении, перпендикулярном к предыдущему. Конь путешествует по своему миру всё дальше и дальше. Наш конь живет на шахматной доске, которая имеет меньшую площадь, чем обычная 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".