소수 동굴

사막 한가운데 솟은 거대한 절벽에서 국제 탐사대가 버려진 석굴 사원을 찾아냈다. 수직 절벽의 중턱에는 작은 동굴이 수없이 파여 있고, 입구는 정사각 격자에 맞춰 가지런히 늘어서 있다. 탐사대의 고고학자는 동굴마다 놓인 불상을 보고 흥분했다. 몇몇 동굴에는 불경 두루마리까지 숨겨져 있었다. 천 년도 더 전에 쓰인 것으로 추정되는 이 두루마리는 값을 매길 수 없다.

탐사대장은 두루마리를 최대한 많이 모으려 한다. 그런데 동굴이 절벽 중턱에 있어서 들어가기가 쉽지 않다. 동굴에 들어가는 방법은 헬리콥터에 매달려 내려가는 것뿐이다. 한 동굴에 들어가 탐사를 마치면 바로 아래 동굴, 바로 아래 동굴의 왼쪽 동굴, 바로 아래 동굴의 오른쪽 동굴 가운데 하나로 기어 내려갈 수 있다. 이 동작은 원하는 만큼 반복할 수 있고, 마지막에는 긴 밧줄을 타고 지상으로 내려온다.

한 번 내려가면서 여러 동굴을 탐사하는 셈이다. 그렇다면 어느 동굴을 골라야 할까. 예비 탐사 결과를 분석한 탐사대의 수학자가 두 가지를 알아냈다. 첫째, 동굴에는 그림 1처럼 한가운데부터 바깥으로 소용돌이를 그리며 번호를 매길 수 있다. 한가운데가 1번이고 그 오른쪽이 2번, 2번의 위가 3번이며, 번호는 시계 반대 방향으로 감겨 나간다. 둘째, 번호가 소수인 동굴에만 두루마리가 있다. 이런 동굴을 소수 동굴이라 부르고, 그림에서 동그라미로 표시했다.

그림 1: 동굴 번호와 소수 동굴

동굴의 전체 개수와 처음 들어간 동굴이 주어진다. 소수 동굴을 가장 많이 지나는 하강 경로를 찾는 프로그램을 작성하라.

입력은 여러 데이터 집합으로 이루어진다. 각 데이터 집합은 한 줄에 정수 $m$ ($1 \le m \le 10^6$)과 정수 $n$ ($1 \le n \le m$)이 공백으로 구분되어 주어진다. $m$은 동굴의 전체 개수이고, $n$은 탐사를 시작하는 동굴의 번호다. 마지막 데이터 집합 다음 줄에는 0이 두 개 주어진다.

각 데이터 집합마다 $n$번 동굴에서 출발해 소수 동굴을 가장 많이 지나는 경로를 찾아, 그 경로 위의 소수 동굴 개수와 경로에서 마지막으로 지나는 소수 동굴의 번호를 한 줄에 공백으로 구분해 출력한다. 처음 탐사하는 $n$번 동굴도 경로에 포함된다. 그런 경로가 여러 개면 마지막으로 지나는 소수 동굴의 번호가 가장 큰 경로를 기준으로 출력한다. 소수 동굴을 하나도 지나지 못하면 0 0을 출력한다.