Шахматы
Слон - это шахматная фигура, которая ходит только по диагонали. Известно, что слоны могут добраться только до клеток одного цвета, причем до каждой из них за несколько ходов (считаем что на доске нет других фигур). На доске заданы две клетки. Определить, может ли слон достичь одну из них из другой и каким образом. Координаты в шахматах задаются буквой (от 'A' до 'H') и цифрой (от 1 до 8). Буква задает колонку, а цифра строку доски. Шахматная доска, слон и поля, достижимые за один ход:
Входные данные
Первая строка содержит количество тестов. Каждый тест начинается со строки, содержащей начальную позицию X и конечную позицию Y. Каждая позиция задается двумя символами, разделенными пробелом. Буква задает колонку, а число строку. Входные данные не содержат одинаковых тестов.
Выходные данные
Для каждого теста вывести одну строку. Если переместить слона из X в Y за любое число ходов невозможно, то вывести "Impossible". Иначе вывести одну из возможных последовательностей ходов от X до Y. Сначала вывести число ходов n (не более 4). Далее вывести n + 1 позицию, описывающих путь слона. Все символы следует разделять одним пробелом. Существует много решений. Любое из них, содержащее не более 4 ходов, допустимо. Напомним, что ходом называется изменение позиции шахматной фигурой (в нашем случае слоном) согласно шахматным правилам (то есть две соседние позиции в выводимой последовательности должны быть разными).