시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 5769 2962 2088 52.968%

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

  • “이제 슬슬 비번 바꿀 때도 됐잖아”
  • “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
  • “그럼 8179로 해”
  • “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
  • “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
  • “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

예제 입력 1

3
1033 8179
1373 8017
1033 1033

예제 출력 1

6
7
0
W3sicHJvYmxlbV9pZCI6IjE5NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHVhY2JkXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWMyMThcdWI5N2MmbmJzcDtcdWM3MjBcdWIwOWNcdWQ3ODhcdWIzYzQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODQgXHVjNTQ0XHVjNzc0XHViNTE0IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yjk3YyA0XHVjNzkwXHViOWFjICZsc3F1bztcdWMxOGNcdWMyMTgmcnNxdW87XHViODVjIFx1YzgxNVx1ZDU3NFx1YjE5M1x1YzU1OFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjZTVjXHVkNTVjIFx1Y2U1Y1x1YWQ2Y1x1YzY0MCBcdWIzMDBcdWQ2NTRcdWI5N2MgXHViMDk4XHViMjA0XHVjNWM4XHViMjk0XHViMzcwOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZsZHF1bztcdWM3NzRcdWM4MWMgXHVjMmFjXHVjMmFjIFx1YmU0NFx1YmM4OCBcdWJjMTRcdWFmYzAgXHViNTRjXHViM2M0IFx1YjQxMFx1Yzc5Nlx1YzU0NCZyZHF1bzs8XC9saT5cclxuXHQ8bGk+JmxkcXVvO1x1Yzc1MSBcdWM5YzBcdWFlMDhcdWM3NDAgMTAzM1x1YzczY1x1Yjg1YyBcdWQ1NzRcdWIxYThcdWIyOTRcdWIzNzAuLi4gXHViMmU0XHVjNzRjIFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWJiMzRcdWM1YzdcdWM3M2NcdWI4NWMgXHVkNTYwXHVjOWMwIFx1YWNlMFx1YmJmY1x1YzkxMVx1Yzc3NFx1YzU3YyZxdW90OzxcL2xpPlxyXG5cdDxsaT4mbGRxdW87XHVhZGY4XHViN2ZjIDgxNzlcdWI4NWMgXHVkNTc0JnJkcXVvOzxcL2xpPlxyXG5cdDxsaT4mbGRxdW87XHVkNzYwLi4uIFx1YzBkZFx1YWMwMSBcdWM4ODAgXHVkNTc0XHViY2ZjXHVhYzhjLiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1Yzg4MCBcdWM3NzRcdWMwYzFcdWQ1NzRcdWMxMWMgXHViZTQ0XHViYzAwXHViYzg4XHVkNjM4XHViOTdjIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVkNTVjIFx1Yzc5MFx1YjlhYyBcdWJjMTZcdWM1ZDAgXHViYWJiIFx1YmMxNFx1YWZiY1x1YjJlOCBcdWI5ZDBcdWM3NzRcdWM1N2MuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViMGI0XHVhYzAwIFx1Y2NhYiBcdWM3OTBcdWI5YWNcdWI5Y2MgXHViYzE0XHVhZmI4XHViYTc0IDgwMzNcdWM3NzQgXHViNDE4XHViMmM4XHVhZTRjIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWM3OTZcdWM1NDQuIFx1YzVlY1x1YjdlYyBcdWIyZThcdWFjYzRcdWI5N2MgXHVhYzcwXHVjY2QwXHVjNTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YWM4MyBcdWFjMTlcdWM3NDBcdWIzNzAuLi4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NC4uLiAxMDMzIDE3MzMgMzczMyAzNzM5IDM3NzkgODc3OSA4MTc5XHVjYzk4XHViN2ZjIFx1YjlkMFx1Yzc3NFx1YzU3Yy4mcmRxdW87PFwvbGk+XHJcblx0PGxpPiZsZHF1bztcdWQ3NjAuLi5cdWM1ZWRcdWMyZGMgXHVjMThjXHVjMjE4XHVjNWQwIFx1YmJmOFx1Y2NlNFx1YWQ3MC4gXHVhZGY4XHViN2ZjIFx1YzU0NFx1YzYwOCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjOWRjXHVjOWMwIFx1YWRmOFx1Yjc5OC4gXHViMTI0IFx1Yzc5MFx1YjlhYyBcdWMxOGNcdWMyMTggXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDRcdWMxMWMgXHViYzE0XHVhZmI4XHViMjk0XHViMzcwIFx1YmE4NyBcdWIyZThcdWFjYzRcdWIwOTggXHVkNTQ0XHVjNjk0XHVkNTVjXHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWM4YyBcdWI5ZDBcdWM1N2MuJnJkcXVvOzxcL2xpPlxyXG5cdDxsaT4mbGRxdW87XHVhZGMwXHVjYzJlXHVjNTQ0JnJkcXVvOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWRmOFx1YjgwN1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViMTI0IFx1Yzc5MFx1YjlhYyBcdWMxOGNcdWMyMThcdWI5Y2MoMTAwMCBcdWM3NzRcdWMwYzEpIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHVjMThjXHVjMjE4IEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjXHViM2M0IFx1ZDU2ZFx1YzBjMSBcdWIxMjQgXHVjNzkwXHViOWFjIFx1YzE4Y1x1YzIxOFx1Yzc4NFx1Yzc0NCBcdWM3MjBcdWM5YzBcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCAmbHNxdW87XHViMTI0IFx1Yzc5MFx1YjlhYyBcdWMyMTgmcnNxdW87XHViNzdjIFx1ZDU1OFx1YzYwMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMDAzOSBcdWM2NDAgXHVhYzE5XHVjNzQwIDEwMDAgXHViYmY4XHViOWNjXHVjNzU4IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWQ1YzhcdWM2YTlcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCB0ZXN0IGNhc2VcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgVFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1YzkwNFx1YzVkMCAxXHVjMzBkXHVjNTI5IFx1YjEyNCBcdWM3OTBcdWI5YWMgXHVjMThjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgdGVzdCBjYXNlXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWI0NTAgXHVjMThjXHVjMjE4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWJjYzBcdWQ2NThcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwIEltcG9zc2libGVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltZSBQYXRoIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbWluaXN0ZXJzIG9mIHRoZSBjYWJpbmV0IHdlcmUgcXVpdGUgdXBzZXQgYnkgdGhlIG1lc3NhZ2UgZnJvbSB0aGUgQ2hpZWYgb2YgU2VjdXJpdHkgc3RhdGluZyB0aGF0IHRoZXkgd291bGQgYWxsIGhhdmUgdG8gY2hhbmdlIHRoZSBmb3VyLWRpZ2l0IHJvb20gbnVtYmVycyBvbiB0aGVpciBvZmZpY2VzLjxcL3A+XHJcblxyXG48cD4mbWRhc2g7IEl0IGlzIGEgbWF0dGVyIG9mIHNlY3VyaXR5IHRvIGNoYW5nZSBzdWNoIHRoaW5ncyBldmVyeSBub3cgYW5kIHRoZW4sIHRvIGtlZXAgdGhlIGVuZW15IGluIHRoZSBkYXJrLjxcL3A+XHJcblxyXG48cD4mbWRhc2g7IEJ1dCBsb29rLCBJIGhhdmUgY2hvc2VuIG15IG51bWJlciAxMDMzIGZvciBnb29kIHJlYXNvbnMuIEkgYW0gdGhlIFByaW1lIG1pbmlzdGVyLCB5b3Uga25vdyE8XC9wPlxyXG5cclxuPHA+Jm1kYXNoOyBJIGtub3csIHNvIHRoZXJlZm9yZSB5b3VyIG5ldyBudW1iZXIgODE3OSBpcyBhbHNvIGEgcHJpbWUuIFlvdSB3aWxsIGp1c3QgaGF2ZSB0byBwYXN0ZSBmb3VyIG5ldyBkaWdpdHMgb3ZlciB0aGUgZm91ciBvbGQgb25lcyBvbiB5b3VyIG9mXHVmYjAxY2UgZG9vci48XC9wPlxyXG5cclxuPHA+Jm1kYXNoOyBObywgaXQmcnNxdW87cyBub3QgdGhhdCBzaW1wbGUuIFN1cHBvc2UgdGhhdCBJIGNoYW5nZSB0aGUgXHVmYjAxcnN0IGRpZ2l0IHRvIGFuIDgsIHRoZW4gdGhlIG51bWJlciB3aWxsIHJlYWQgODAzMyB3aGljaCBpcyBub3QgYSBwcmltZSE8XC9wPlxyXG5cclxuPHA+Jm1kYXNoOyBJIHNlZSwgYmVpbmcgdGhlIHByaW1lIG1pbmlzdGVyIHlvdSBjYW5ub3Qgc3RhbmQgaGF2aW5nIGEgbm9uLXByaW1lIG51bWJlciBvbiB5b3VyIGRvb3IgZXZlbiBmb3IgYSBmZXcgc2Vjb25kcy48XC9wPlxyXG5cclxuPHA+Jm1kYXNoOyBDb3JyZWN0ISBTbyBJIG11c3QgaW52ZW50IGEgc2NoZW1lIGZvciBnb2luZyBmcm9tIDEwMzMgdG8gODE3OSBieSBhIHBhdGggb2YgcHJpbWUgbnVtYmVycyB3aGVyZSBvbmx5IG9uZSBkaWdpdCBpcyBjaGFuZ2VkIGZyb20gb25lIHByaW1lIHRvIHRoZSBuZXh0IHByaW1lLjxcL3A+XHJcblxyXG48cD5Ob3csIHRoZSBtaW5pc3RlciBvZiBmaW5hbmNlLCB3aG8gaGFkIGJlZW4gZWF2ZXNkcm9wcGluZywgaW50ZXJ2ZW5lZC48XC9wPlxyXG5cclxuPHA+Jm1kYXNoOyBObyB1bm5lY2Vzc2FyeSBleHBlbmRpdHVyZSwgcGxlYXNlISBJIGhhcHBlbiB0byBrbm93IHRoYXQgdGhlIHByaWNlIG9mIGEgZGlnaXQgaXMgb25lIHBvdW5kLjxcL3A+XHJcblxyXG48cD4mbWRhc2g7IEhtbSwgaW4gdGhhdCBjYXNlIEkgbmVlZCBhIGNvbXB1dGVyIHByb2dyYW0gdG8gbWluaW1pemUgdGhlIGNvc3QuIFlvdSBkb24mcnNxdW87dCBrbm93IHNvbWUgdmVyeSBjaGVhcCBzb2Z0d2FyZSBndXJ1cywgZG8geW91PzxcL3A+XHJcblxyXG48cD4mbWRhc2g7IEluIGZhY3QsIEkgZG8uIFlvdSBzZWUsIHRoZXJlIGlzIHRoaXMgcHJvZ3JhbW1pbmcgY29udGVzdCBnb2luZyBvbi4uLjxcL3A+XHJcblxyXG48cD5IZWxwIHRoZSBwcmltZSBtaW5pc3RlciB0byBcdWZiMDFuZCB0aGUgY2hlYXBlc3QgcHJpbWUgcGF0aCBiZXR3ZWVuIGFueSB0d28gZ2l2ZW4gZm91ci1kaWdpdCBwcmltZXMhIFRoZSBmaXJzdCBkaWdpdCBtdXN0IGJlIG5vbnplcm8sIG9mIGNvdXJzZS4gSGVyZSBpcyBhIHNvbHV0aW9uIGluIHRoZSBjYXNlIGFib3ZlLjxcL3A+XHJcblxyXG48cHJlPlxyXG4xMDMzXHJcbjE3MzNcclxuMzczM1xyXG4zNzM5XHJcbjM3NzlcclxuODc3OVxyXG44MTc5PFwvcHJlPlxyXG5cclxuPHA+VGhlIGNvc3Qgb2YgdGhpcyBzb2x1dGlvbiBpcyA2IHBvdW5kcy4gTm90ZSB0aGF0IHRoZSBkaWdpdCAxIHdoaWNoIGdvdCBwYXN0ZWQgb3ZlciBpbiBzdGVwIDIgY2FuIG5vdCBiZSByZXVzZWQgaW4gdGhlIGxhc3Qgc3RlcCAmbmRhc2g7IGEgbmV3IDEgbXVzdCBiZSBwdXJjaGFzZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbmUgbGluZSB3aXRoIGEgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKGF0IG1vc3QgMTAwKS4gVGhlbiBmb3IgZWFjaCB0ZXN0IGNhc2UsIG9uZSBsaW5lIHdpdGggdHdvIG51bWJlcnMgc2VwYXJhdGVkIGJ5IGEgYmxhbmsuIEJvdGggbnVtYmVycyBhcmUgZm91ci1kaWdpdCBwcmltZXMgKHdpdGhvdXQgbGVhZGluZyB6ZXJvcykuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T25lIGxpbmUgZm9yIGVhY2ggY2FzZSwgZWl0aGVyIHdpdGggYSBudW1iZXIgc3RhdGluZyB0aGUgbWluaW1hbCBjb3N0IG9yIGNvbnRhaW5pbmcgdGhlIHdvcmQgSW1wb3NzaWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=