소수 나선

지루함은 때로 창의력의 원천이 된다. 폴란드 수학자 Stanislaw Ulam(1909-1984)은 "길고도 지루한 발표"를 들으면서 그 이름을 딴 울람 나선을 발견했다. 그는 격자 위에 양의 정수를 한 칸에 하나씩 나선 모양으로 적는 것으로 시작했다. 그런 다음 합성수(즉 소수가 아닌 수)를 지웠다. 그가 발견한 흥미로운 성질은 남은 소수들이 격자의 여러 대각선을 따라 줄지어 나타나는 듯하다는 것이었다.

모든 양의 정수	소수만

두 그림 모두 무한히 큰 격자이지만, 물리적인 제약 때문에 이 공간에는 유한한 일부만 들어간다.

위의 두 번째 격자(울람 나선) 위를 이동한다고 하자. 합성수가 들어 있는 칸으로는 자유롭게 이동할 수 있지만, 소수가 들어 있는 칸으로는 이동할 수 없다. 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있고 대각선으로는 이동할 수 없다. 두 합성수 사이의 최단 경로 길이를 구하는 프로그램을 작성하라. 경로가 존재하지 않을 수도 있다. 예를 들어 12와 72가 적힌 칸에서는 다른 어떤 합성수 칸으로도 이동할 수 없다. 경로의 길이는 경로 위의 걸음 수이다.

각 테스트 케이스는 격자 위의 두 칸을 나타내는 두 정수 1 ≤ x, y ≤ 10,000이 한 줄에 주어진다. 입력값에는 제한이 있지만, x와 y 사이의 경로는 전혀 제한되지 않는다.

각 케이스마다 케이스 번호와 함께 칸 x와 y 사이의 최단 경로 길이를 출력하라. 경로가 존재하지 않으면 "impossible"을 출력하라.