7195 : 소수 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 개의 4자리 소수가 주어집니다. 한 번에 하나의 자릿수만 변경하여 다른 소수로 변환할 때, 첫 번째 소수에서 두 번째 소수로 가기 위한 최소 변환 횟수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 테스트 케이스의 개수 T가 주어집니다.
다음 T개의 줄에 걸쳐 각 줄마다 서로 다른 두 개의 4자리 소수가 주어집니다.
다음 T개의 줄에 걸쳐 각 줄마다 서로 다른 두 개의 4자리 소수가 주어집니다.
출력 설명
최소 변환 횟수를 출력합니다. 변환이 불가능하면 Impossible을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1033 8179
1373 8017
1033 1033
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6
7
0도움
1033 → 1733 → 3733 → 3739 → 3779 → 8779 → 8179 와 같은 소수 경로를 통해 6번 만에 도달합니다.