만료된 라이선스

Paul은 방금 독일의 유명 대학에서 석사 학위를 마친 매우 뛰어난 컴퓨터 과학자이다. 이제 그는 박사 과정으로 학문적 경력을 마무리하려고 한다. 문제는 훌륭한 대학이 너무 많아서 어느 곳이 최선인지 고르기 어렵다는 것이다. 일부 지원 마감이 곧 다가오기 때문에, Paul이 결정을 미룰 수 있는 유일한 방법은 그냥 모든 대학에 지원하는 것이다.

대부분의 지원서에는 증명사진을 첨부해야 한다. 그런데 이런 사진의 종횡비에 대한 국제 표준은 없는 것 같다. 대부분의 유럽 대학은 Paul에게 종횡비 4.5 대 6의 사진을 보내라고 요구하지만, 일부 아시아 국가는 사진의 종횡비가 정확히 7.14 대 11.22가 아니면 지원서를 즉시 폐기한다.

Paul은 사진 편집에 관심이 없었기 때문에 제대로 된 소프트웨어에 돈을 쓸 이유도 없었다. 몇 달 전 무료 체험판을 내려받았지만 그 버전은 이미 만료되어 이제는 우스꽝스러운 제약 아래에서만 동작한다. 예를 들어 자르기 도구는 이제 종횡비를 설정할 때 임의의 숫자를 받지 않고 소수만 받는다. 그래서 Paul은 원하는 종횡비를 두 소수로 제대로 나타낼 수 있는지 궁금해졌다. 물론 이것이 가능하다면, 그가 입력해야 하는 소수도 알고 싶어 한다.

입력은 다음과 같다.

• Paul이 제출해야 하는 지원서의 수 n (1 ≤ n ≤ 105)이 있는 한 줄;
• n개의 줄. 각 줄에는 두 실수 a와 b (0 < a, b < 100)가 있으며, a × b는 한 지원서에서 원하는 종횡비이다.

모든 실수는 소수점 아래 최대 5자리까지 주어진다.

각 지원서에 대해, 원하는 종횡비를 두 소수 p와 q로 나타낼 수 있으면 p와 q를 한 줄에 출력한다. 그렇지 않으면 impossible을 출력한다. 여러 해가 존재하면 p + q를 최소화하는 해를 출력한다.