시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 135 71 53 51.456%

문제

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

체스판 위의 두 좌표가 주어진다. 이 때, 비숍이 한 좌표에서 다른 좌표로 이동할 수 있는지와 그 방법을 구하는 프로그램을 작성하시오. 체스판의 좌표는 글자(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
W3sicHJvYmxlbV9pZCI6IjkyMDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2NiNFx1YzJhNFx1YzVkMFx1YzExYyBcdWJlNDRcdWMyMGRcdWM3NDAgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjXHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjlkMFx1Yzc3NFx1YjJlNC4gXHViZTQ0XHVjMjBkXHVjNzQwIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVhYzAwXHVjOWMwXHViMjk0IFx1Y2U3OFx1Yzc0MCBcdWJhODcgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWIyZTRcdWI5NzggXHViOWQwXHVjNzQwIFx1YzVjNlx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM3NTggXHViNDUwIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmU0NFx1YzIwZFx1Yzc3NCBcdWQ1NWMgXHVjODhjXHVkNDVjXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWM2NDAgXHVhZGY4IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFlMDBcdWM3OTAoQS1IKVx1YzY0MCBcdWMyMmJcdWM3OTAoMS04KVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM1ZjRcdWM1ZDAsIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1ODlcdWM1ZDAgXHVjODAxXHVkNjAwXHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlc3MucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI4cHg7IHdpZHRoOjIyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48c3Ryb25nPlx1YWRmOFx1YjliYyAxPFwvc3Ryb25nPiZuYnNwOyZuZGFzaDsgXHVjY2I0XHVjMmE0XHVkMzEwLCBcdWJlNDRcdWMyMGQsIFx1YmU0NFx1YzIwZFx1Yzc3NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1ODxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IFhcdWM2NDAgXHViM2M0XHVjYzI5IFx1YzcwNFx1Y2U1OCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWI0NTAgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjNWY0LCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTg5XHVjNzc0XHViMmU0LiBcdWM5MTFcdWJjZjVcdWI0MThcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWJlNDRcdWMyMGRcdWM3NzQgWFx1YzVkMFx1YzExYyBZXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0ICYjMzk7SW1wb3NzaWJsZSYjMzk7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NThcdWJhNzQsIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgXHViYTNjXHVjODAwIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1Yzc4NVx1YjgyNSBcdWQ2MTVcdWMyZGRcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzggXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDVjXHViMzAwIDRcdWJjODggXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3YyBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTIwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNoZXNzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBjaGVzcyB0aGUgYmlzaG9wIGlzIHRoZSBjaGVzc21hbiwgd2hpY2ggY2FuIG9ubHkgbW92ZSBkaWFnb25hbC4gSXQgaXMgd2VsbCBrbm93biB0aGF0IGJpc2hvcHMgY2FuIHJlYWNoIG9ubHkgZmllbGRzIG9mIG9uZSBjb2xvciBidXQgYWxsIG9mIHRoZW0gaW4gc29tZSBudW1iZXIgb2YgbW92ZXMgKGFzc3VtaW5nIG5vIG90aGVyIGZpZ3VyZXMgYXJlIG9uIHRoZSBmaWVsZCkuIFlvdSBhcmUgZ2l2ZW4gdHdvIGNvb3JkaW5hdGVzIG9uIGEgY2hlc3MtZmllbGQgYW5kIHNob3VsZCBkZXRlcm1pbmUsIGlmIGEgYmlzaG9wIGNhbiByZWFjaCB0aGUgb25lIGZpZWxkIGZyb20gdGhlIG90aGVyIGFuZCBob3cuIENvb3JkaW5hdGVzIGluIGNoZXNzIGFyZSBnaXZlbiBieSBhIGxldHRlciAoJnJzcXVvO0EmcnNxdW87IHRvICZyc3F1bztIJnJzcXVvOykgYW5kIGEgbnVtYmVyICgxIHRvIDgpLiBUaGUgbGV0dGVyIHNwZWNpZmllcyB0aGUgY29sdW1uLCB0aGUgbnVtYmVyIHRoZSByb3cgb24gdGhlIGNoZXNzYm9hcmQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoZXNzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyOHB4OyB3aWR0aDoyMjZweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PHN0cm9uZz5GaWd1cmUgMTxcL3N0cm9uZz4gJm5kYXNoOyBDaGVzc2JvYXJkLCBiaXNob3AgYW5kIGZpZWxkcyB0aGUgYmlzaG9wIGNhbiByZWFjaCBpbiBvbmUgbW92ZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUsIGNvbnRhaW5pbmcgdGhlIHN0YXJ0IHBvc2l0aW9uIFggYW5kIGVuZCBwb3NpdGlvbiBZIC4gRWFjaCBwb3NpdGlvbiBpcyBnaXZlbiBieSB0d28gc3BhY2Ugc2VwYXJhdGVkIGNoYXJhY3RlcnMuIEEgbGV0dGVyIGZvciB0aGUgY29sdW1uIGFuZCBhIG51bWJlciBmb3IgdGhlIHJvdy4gVGhlcmUgYXJlIG5vIGR1cGxpY2F0ZSB0ZXN0IGNhc2VzIGluIG9uZSBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgZm9yIGV2ZXJ5IHRlc3QgY2FzZS4gSWYgaXQmcnNxdW87cyBub3QgcG9zc2libGUgdG8gbW92ZSBhIGJpc2hvcCBmcm9tIFggdG8gWSBpbiBhbnkgbnVtYmVyIG9mIG1vdmVzIG91dHB1dCAmcnNxdW87SW1wb3NzaWJsZSZyc3F1bzsuIE90aGVyd2lzZSBvdXRwdXQgb25lIHBvc3NpYmxlIG1vdmUgc2VxdWVuY2UgZnJvbSBYIHRvIFkgLiBPdXRwdXQgdGhlIG51bWJlciBuIG9mIG1vdmVzIGZpcnN0IChhbGxvd2VkIHRvIGJlIDQgYXQgbW9zdCkuIEZvbGxvd2VkIGJ5IG4gKyAxIHBvc2l0aW9ucywgd2hpY2ggZGVzY3JpYmUgdGhlIHBhdGggdGhlIGJpc2hvcCBoYXMgdG8gZ28uIEV2ZXJ5IGNoYXJhY3RlciBpcyBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLiBUaGVyZSBhcmUgbWFueSBwb3NzaWJsZSBzb2x1dGlvbnMuIEFueSB3aXRoIGF0IG1vc3QgNCBtb3ZlcyB3aWxsIGJlIGFjY2VwdGVkLiBSZW1lbWJlciB0aGF0IGluIGEgY2hlc3MgbW92ZSBvbmUgY2hlc3NtYW4gKHRoZSBiaXNob3AgaW4gdGhpcyBjYXNlKSBoYXMgdG8gY2hhbmdlIGhpcyBwb3NpdGlvbiB0byBiZSBhIHZhbGlkIG1vdmUgKGkuZS4gdHdvIGNvbnNlY3V0aXZlIHBvc2l0aW9ucyBpbiB0aGUgb3V0cHV0IG11c3QgZGlmZmVyKTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==