못된 택쌤은 학생들에게 이상한 문제를 내고 그 문제를 못 풀면 놀리는 것을 즐긴다.

솔이는 못된 택쌤에게 복수하기 위해 오늘 낼 문제를 미리 알아내서,

그 문제를 풀 수 있는 프로그램을 미리 작성하려고 한다.

솔이가 열심히 염탐한 결과, 택쌤이 오늘 낼 문제는 다음과 같다.

10^7이하의 양의 정수 n이 주어졌을 때, n의 1이 아닌 약수 중 두 개를 고른다. 이를 각각 d_1, d_2라고 하자.

(d_1 = d_2이어도 상관없다.)

이 때 (d_1+d_2)과 n의 최대공약수가 1인 n의 두 약수 d_1, d_2를 찾을 수 있는가?

택쌤이 어떤 n값을 문제로 낼지 모르기 때문에, 최대 30만개의 n값에 대해서도 잘 돌아가는 프로그램을 작성해 보자.

택쌤에게 복수하기 timer 2s memory 256MB

택쌤에게 복수하기 2s 256MB