소수 경로
면접 대비시간 제한2초메모리 제한256 MB
네 자리 소수 A를 B로 바꿀 때 매 단계마다 결과가 항상 네 자리 소수가 되도록 한 자리씩 바꾸는 최소 횟수를 BFS로 구하는 문제입니다.
문제
창영이는 소수를 매우 좋아해서 게임 비밀번호를 네 자리 소수로 정해 두었다. 이제 비밀번호를 다른 네 자리 소수로 바꾸려고 한다.
이 게임에서는 한 번에 숫자 한 자리만 바꿀 수 있다. 그리고 바꾼 뒤의 비밀번호도 항상 네 자리 소수여야 한다. 첫 자리를 0으로 바꾸어 1000보다 작은 수를 만드는 것은 네 자리 수가 아니므로 허용되지 않는다.
두 네 자리 소수 A와 B가 주어졌을 때, A에서 B로 바꾸는 데 필요한 최소 변경 횟수를 구하시오. 한 가능한 변환은 1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179처럼 모든 중간 값이 네 자리 소수인 순서이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄에는 각 테스트 케이스마다 두 네 자리 소수 A와 B가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 A에서 B로 바꾸는 데 필요한 최소 변경 횟수를 한 줄에 하나씩 출력한다. 변환할 수 없다면 Impossible을 출력한다.