Paul은 독일의 명문 대학에서 최근에 석사 학위를 받은, 엄청난 재능을 가진 컴퓨터 과학자입니다. 이제 Paul은 박사 과정에서 학업 경력을 계속 이어가려 합니다. 문제는 좋은 대학들이 너무나 많은 나머지 그에게 최고의 대학을 뽑는 일은 너무나 어렵다는 것입니다. 일부 대학들의 원서 접수 마감기한이 다가오고 있기 때문에, Paul이 이러한 결정을 늦추는 유일한 방법은 그냥 모든 학교에 원서를 제출하는 것입니다.
대부분의 학교들은 Paul에게 증명사진을 붙일 것을 요구합니다. 하지만 증명사진의 가로와 세로 비율에는 국제 표준이 존재하지 않는 것으로 보입니다. 대부분의 유럽 대학들은 증명사진의 가로와 세로 비율을 4.5 대 6으로 맞출 것을 요구하지만, 몇몇 아시아 국가들은 7.14 대 11.22로 맞출 것을 요구합니다.
Paul은 사진 편집에 관심이 없기 때문에, 적절한 소프트웨어에 많은 돈을 지불할 이유가 없었습니다. 그는 이미 몇 달 전에 무료 체험판을 다운로드받았지만, 무료 체험은 이미 끝났으며 여러 웃긴 제한이 걸린 상태로 소프트웨어를 사용할 수 있습니다. 예를 들어, '잘라내기' 도구는 더 이상 가로-세로 비율에 임의의 숫자를 입력할 수 없으며 오직 소수(素數; prime numbers)만 입력할 수 있습니다. 이로 인해 Paul은 원하는 가로-세로 비율이 2개의 소수로 제대로 표현될 수 있는지 궁금해합니다. 물론 제대로 표현이 가능하다면, 어떤 소수를 입력해야 하는지도 알고 싶습니다.
--------
[입력]
입력은 다음과 같이 구성되어 있습니다.
1번째 줄에는 Paul이 제출해야 하는 원서에 붙여야 할 증명사진의 개수를 나타내는 정수 n (1 ≤ n ≤ 105)이 주어집니다.
다음 n개 줄에는 각 증명사진마다 희망하는 가로-세로 비율 a × b를 나타내는 두 실수 a와 b (0 < a, b < 100)가 주어집니다.
이때 입력되는 모든 실수는 소수점 아래 자릿수가 최대 5자리입니다.
--------
[출력]
각 증명사진마다 희망하는 가로-세로 비율을 두 소수 p와 q로 표현하는 것이 가능하다면, p와 q를 한 줄에 출력합니다. (만약 서로 다른 2가지 이상의 방법으로 표현할 수 있다면, p + q의 값이 가장 작은 것을 출력해야 합니다.) 만약 불가능하다면, "impossible"을 출력합니다.
moner_ari 1년 전
[문제]
Paul은 독일의 명문 대학에서 최근에 석사 학위를 받은, 엄청난 재능을 가진 컴퓨터 과학자입니다. 이제 Paul은 박사 과정에서 학업 경력을 계속 이어가려 합니다. 문제는 좋은 대학들이 너무나 많은 나머지 그에게 최고의 대학을 뽑는 일은 너무나 어렵다는 것입니다. 일부 대학들의 원서 접수 마감기한이 다가오고 있기 때문에, Paul이 이러한 결정을 늦추는 유일한 방법은 그냥 모든 학교에 원서를 제출하는 것입니다.
대부분의 학교들은 Paul에게 증명사진을 붙일 것을 요구합니다. 하지만 증명사진의 가로와 세로 비율에는 국제 표준이 존재하지 않는 것으로 보입니다. 대부분의 유럽 대학들은 증명사진의 가로와 세로 비율을 4.5 대 6으로 맞출 것을 요구하지만, 몇몇 아시아 국가들은 7.14 대 11.22로 맞출 것을 요구합니다.
Paul은 사진 편집에 관심이 없기 때문에, 적절한 소프트웨어에 많은 돈을 지불할 이유가 없었습니다. 그는 이미 몇 달 전에 무료 체험판을 다운로드받았지만, 무료 체험은 이미 끝났으며 여러 웃긴 제한이 걸린 상태로 소프트웨어를 사용할 수 있습니다. 예를 들어, '잘라내기' 도구는 더 이상 가로-세로 비율에 임의의 숫자를 입력할 수 없으며 오직 소수(素數; prime numbers)만 입력할 수 있습니다. 이로 인해 Paul은 원하는 가로-세로 비율이 2개의 소수로 제대로 표현될 수 있는지 궁금해합니다. 물론 제대로 표현이 가능하다면, 어떤 소수를 입력해야 하는지도 알고 싶습니다.
--------
[입력]
입력은 다음과 같이 구성되어 있습니다.
이때 입력되는 모든 실수는 소수점 아래 자릿수가 최대 5자리입니다.
--------
[출력]
각 증명사진마다 희망하는 가로-세로 비율을 두 소수 p와 q로 표현하는 것이 가능하다면, p와 q를 한 줄에 출력합니다. (만약 서로 다른 2가지 이상의 방법으로 표현할 수 있다면, p + q의 값이 가장 작은 것을 출력해야 합니다.) 만약 불가능하다면, "impossible"을 출력합니다.