시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB61026720846.222%

문제

체스에서 비숍은 대각선으로만 움직일 수 있는 말이다. 비숍은 현재 있는 칸과 같은 색상을 가지는 칸은 몇 번 움직이면 이동할 수 있다. (체스판에 다른 말은 없다고 가정한다)

체스판 위의 두 좌표가 주어진다. 이때, 비숍이 한 좌표에서 다른 좌표로 이동할 수 있는지와 그 방법을 구하는 프로그램을 작성하시오. 체스판의 좌표는 글자(A-H)와 숫자(1-8)로 나타내며, 글자는 열에, 숫자는 행에 적혀져 있다.

그림 1 – 체스판, 비숍, 비숍이 한 번에 움직일 수 있는 위치

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 시작 위치 X와 도착 위치 Y가 주어진다. 각 위치는 두 글자가 공백으로 구분되어져 있다. 글자는 열, 숫자는 행이다. 중복되는 테스트 케이스는 주어지지 않는다. 

출력

각 테스트 케이스에 대해서 한 줄을 출력한다. 만약, 비숍이 X에서 Y로 이동할 수 없으면 'Impossible'을 출력한다. 이 경우를 제외하면, 움직이는 방법을 출력한다.

움직일 수 있을 때는 먼저 움직인 횟수를 출력한다. 그 다음에는 입력 형식과 같은 형식으로 움직인 방법을 출력한다. 최대 4번 움직일 수 있으며, 가능한 경우가 여러 개일 때에는 아무거나 출력하면 된다.

예제 입력 1

3
E 2 E 3
F 1 E 8
A 3 A 3

예제 출력 1

Impossible
2 F 1 B 5 E 8
0 A 3
W3sicHJvYmxlbV9pZCI6IjkyMDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2NiNFx1YzJhNFx1YzVkMFx1YzExYyBcdWJlNDRcdWMyMGRcdWM3NDAgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjXHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjlkMFx1Yzc3NFx1YjJlNC4gXHViZTQ0XHVjMjBkXHVjNzQwIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVhYzAwXHVjOWMwXHViMjk0IFx1Y2U3OFx1Yzc0MCBcdWJhODcgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWIyZTRcdWI5NzggXHViOWQwXHVjNzQwIFx1YzVjNlx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM3NTggXHViNDUwIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViZTQ0XHVjMjBkXHVjNzc0IFx1ZDU1YyBcdWM4OGNcdWQ0NWNcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1Yzg4Y1x1ZDQ1Y1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1YzY0MCBcdWFkZjggXHViYzI5XHViYzk1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YWUwMFx1Yzc5MChBLUgpXHVjNjQwIFx1YzIyYlx1Yzc5MCgxLTgpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVhZTAwXHVjNzkwXHViMjk0IFx1YzVmNFx1YzVkMCwgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU4OVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVzcy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjhweDsgd2lkdGg6MjI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxzdHJvbmc+XHVhZGY4XHViOWJjIDE8XC9zdHJvbmc+Jm5ic3A7Jm5kYXNoOyBcdWNjYjRcdWMyYTRcdWQzMTAsIFx1YmU0NFx1YzIwZCwgXHViZTQ0XHVjMjBkXHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggWFx1YzY0MCBcdWIzYzRcdWNjMjkgXHVjNzA0XHVjZTU4IFlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjNzA0XHVjZTU4XHViMjk0IFx1YjQ1MCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM1ZjQsIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1ODlcdWM3NzRcdWIyZTQuIFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmU0NFx1YzIwZFx1Yzc3NCBYXHVjNWQwXHVjMTFjIFlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJhNzQgJiMzOTtJbXBvc3NpYmxlJiMzOTtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YmE3NCwgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWJhM2NcdWM4MDAgXHVjNmMwXHVjOWMxXHVjNzc4IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1IFx1ZDYxNVx1YzJkZFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkNWNcdWIzMDAgNFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5MjA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hlc3MiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGNoZXNzIHRoZSBiaXNob3AgaXMgdGhlIGNoZXNzbWFuLCB3aGljaCBjYW4gb25seSBtb3ZlIGRpYWdvbmFsLiBJdCBpcyB3ZWxsIGtub3duIHRoYXQgYmlzaG9wcyBjYW4gcmVhY2ggb25seSBmaWVsZHMgb2Ygb25lIGNvbG9yIGJ1dCBhbGwgb2YgdGhlbSBpbiBzb21lIG51bWJlciBvZiBtb3ZlcyAoYXNzdW1pbmcgbm8gb3RoZXIgZmlndXJlcyBhcmUgb24gdGhlIGZpZWxkKS4gWW91IGFyZSBnaXZlbiB0d28gY29vcmRpbmF0ZXMgb24gYSBjaGVzcy1maWVsZCBhbmQgc2hvdWxkIGRldGVybWluZSwgaWYgYSBiaXNob3AgY2FuIHJlYWNoIHRoZSBvbmUgZmllbGQgZnJvbSB0aGUgb3RoZXIgYW5kIGhvdy4gQ29vcmRpbmF0ZXMgaW4gY2hlc3MgYXJlIGdpdmVuIGJ5IGEgbGV0dGVyICgmcnNxdW87QSZyc3F1bzsgdG8gJnJzcXVvO0gmcnNxdW87KSBhbmQgYSBudW1iZXIgKDEgdG8gOCkuIFRoZSBsZXR0ZXIgc3BlY2lmaWVzIHRoZSBjb2x1bW4sIHRoZSBudW1iZXIgdGhlIHJvdyBvbiB0aGUgY2hlc3Nib2FyZC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlc3MucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI4cHg7IHdpZHRoOjIyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48c3Ryb25nPkZpZ3VyZSAxPFwvc3Ryb25nPiAmbmRhc2g7IENoZXNzYm9hcmQsIGJpc2hvcCBhbmQgZmllbGRzIHRoZSBiaXNob3AgY2FuIHJlYWNoIGluIG9uZSBtb3ZlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSwgY29udGFpbmluZyB0aGUgc3RhcnQgcG9zaXRpb24gWCBhbmQgZW5kIHBvc2l0aW9uIFkgLiBFYWNoIHBvc2l0aW9uIGlzIGdpdmVuIGJ5IHR3byBzcGFjZSBzZXBhcmF0ZWQgY2hhcmFjdGVycy4gQSBsZXR0ZXIgZm9yIHRoZSBjb2x1bW4gYW5kIGEgbnVtYmVyIGZvciB0aGUgcm93LiBUaGVyZSBhcmUgbm8gZHVwbGljYXRlIHRlc3QgY2FzZXMgaW4gb25lIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBmb3IgZXZlcnkgdGVzdCBjYXNlLiBJZiBpdCZyc3F1bztzIG5vdCBwb3NzaWJsZSB0byBtb3ZlIGEgYmlzaG9wIGZyb20gWCB0byBZIGluIGFueSBudW1iZXIgb2YgbW92ZXMgb3V0cHV0ICZyc3F1bztJbXBvc3NpYmxlJnJzcXVvOy4gT3RoZXJ3aXNlIG91dHB1dCBvbmUgcG9zc2libGUgbW92ZSBzZXF1ZW5jZSBmcm9tIFggdG8gWSAuIE91dHB1dCB0aGUgbnVtYmVyIG4gb2YgbW92ZXMgZmlyc3QgKGFsbG93ZWQgdG8gYmUgNCBhdCBtb3N0KS4gRm9sbG93ZWQgYnkgbiArIDEgcG9zaXRpb25zLCB3aGljaCBkZXNjcmliZSB0aGUgcGF0aCB0aGUgYmlzaG9wIGhhcyB0byBnby4gRXZlcnkgY2hhcmFjdGVyIGlzIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UuIFRoZXJlIGFyZSBtYW55IHBvc3NpYmxlIHNvbHV0aW9ucy4gQW55IHdpdGggYXQgbW9zdCA0IG1vdmVzIHdpbGwgYmUgYWNjZXB0ZWQuIFJlbWVtYmVyIHRoYXQgaW4gYSBjaGVzcyBtb3ZlIG9uZSBjaGVzc21hbiAodGhlIGJpc2hvcCBpbiB0aGlzIGNhc2UpIGhhcyB0byBjaGFuZ2UgaGlzIHBvc2l0aW9uIHRvIGJlIGEgdmFsaWQgbW92ZSAoaS5lLiB0d28gY29uc2VjdXRpdmUgcG9zaXRpb25zIGluIHRoZSBvdXRwdXQgbXVzdCBkaWZmZXIpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==