3895: 质数强迫症
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：82
解决：29
题目描述
prime.in/out
小理最近痴迷于数学，他疯狂的喜欢上了质数，他认为质数是世界上最漂亮、最完美
的东西，于是他换上了“质数强迫症”，主要症状表现为：他不能见到任何合数，必须保证
他所能看到的数字均为质数。
小理特地选择了一个房间号码为四位质数的酒店房间，将这个初始四位质数记为 a。很
不巧，这一天歹徒控制了这个酒店，酒店中有一位掌握国家机密的高级特工，为了保护这
名特工，酒店决定将所有房间的房间号（四位数）打乱，用数字贴纸贴到原来的房间号上
以覆盖原来的数字。
酒店知道小理的症状，于是给了他一个新的四位质数房号，将这个目标四位质数记为
b。小理在更换房号时发现了问题：他每次只能覆盖四位房号中的一个数字，所以他必须保
证从初始房号 a 到目标房号 b 之间的每一步的数字均为素数。小理想找一个修改次数最少
的方法更换房号。
例如：从 1033 变化至 8179，若直接把“1”改为“8”得到 8033，小理就会因为 8033
不是质数而犯病。
现在这个任务就交给你了。你要从一个四位的质数出发，每次修改其中的一位，并且
要保证修改的结果还是一个质数，还不能出现前导零。你要找到一个修改次数最少的方案，
得到我们所需要的质数。
【样例解释】
关于 1033 怎么变到 8179，这里是一个最短的方策：
1033
1733
3733
3739
3779
8779
8179
共修改了 6 次。
【数据规模与约定】
在 100%的数据中，1000≤a , b≤9999。
输入
一行，两个四位的素数(没有前导零)，表示初始数 a 和目标数 b。
输出
一个数，表示最少的操作次数。如果不可能，输出“Impossible”。
样例输入 复制
1033 8179样例输出 复制
6