외계 지성체에게 다시 보내는 메시지

1974년 11월 16일 토요일 오후, 푸에르토리코의 아레시보 전파 망원경에서 외계 지성체에게 보내는 메시지가 발신되었다. 메시지는 1679비트로 이루어졌고, 23 × 73 픽셀의 직사각형 그림으로 해석되도록 만들어졌다. 23과 73이 모두 소수이므로, 각 변이 1픽셀보다 긴 직사각형 그림의 크기는 23 × 73 하나뿐이다. 물론 수신자가 메시지를 직사각형 그림으로 해석하려 한다는 보장은 없었고, 설령 그렇게 하더라도 픽셀을 잘못 배치할 수도 있었다. 아레시보 메시지를 보낸 사람들은 낙관적이었다.

우리는 비슷한 프로젝트를 계획하고 있다. 이 프로젝트에서 여러분이 맡은 일은 해석된 직사각형 그림의 가장 적합한 가로와 세로를 찾는 것이다. "가장 적합한"의 뜻은 다음과 같다. 4보다 큰 정수 $m$이 주어지고, 1 이하의 양의 분수 $a/b$도 주어진다. 그림의 넓이는 $m$을 넘지 않아야 한다. 그림의 가로와 세로는 모두 소수여야 한다. 가로를 세로로 나눈 비율은 $a/b$ 이상 1 이하여야 한다. 이 조건 아래에서 그림의 넓이를 최대로 만들어야 한다.

다시 말해, 정수 $m$과 분수 $a/b$가 주어진다. $m > 4$이고 $0 < a/b \le 1$이다. $pq \le m$이고 $a/b \le p/q \le 1$인 소수 쌍 $p$, $q$ 가운데 곱 $pq$가 최대인 쌍을 찾아야 한다. 그 $p$와 $q$가 해석된 그림의 "가장 적합한" 가로와 세로이다.

입력은 최대 2000개의 양의 정수 세 쌍으로 이루어진다. 한 줄에 세 정수가 공백으로 구분되어 하나씩 주어진다. 마지막에는 입력의 끝을 뜻하는 0 0 0이 한 줄 주어지며, 이 줄은 처리하지 않는다.

각 줄의 세 정수는 순서대로 위에서 설명한 정수 $m$, 분자 $a$, 분모 $b$이다. $4 < m < 100000$이고 $1 \le a \le b \le 1000$이다.

입력의 $i$번째 줄에 대한 답을 출력의 $i$번째 줄에 출력한다. 각 줄에는 위에서 설명한 가로 $p$와 세로 $q$를 이 순서대로 공백 하나로 구분해 출력한다. 다른 문자는 출력하지 않는다.