택쌤에게 복수하기

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

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

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

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

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값에 대해서도 잘 돌아가는 프로그램을 작성해 보자.

입력

첫 줄의 테스트케이스의 개수인 T가 주어진다.(1≤T≤300,000)

다음 T줄에 걸쳐, 문제 조건에 설명된 n값이 주어진다. (2≤n≤10^7, 참고로 10^7은 천만이다.)

테스트케이스별로 n값이 모두 다르다는 보장은 없다.

출력

테스트 케이스 별로, 각 줄에, 문제 조건에 맞는 n의 두 약수를 공백을 사이에 두고 출력한다.

답이 여러 개인 경우, 한 가지만 출력하면 된다.

만약 조건에 맞는 두 약수가 없는 경우, NOPE를 출력한다.

예제

출처

Online Contest | ohjtgood

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