시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

On February 15, 2012, the New York Times reported a flaw in the method of generating keys for a public-key encryption system (“Researchers Find a Flaw in a Widely Used Online Encryption Method" by John Markoff). This flaw enables an attacker to determine private keys given a set of flawed public keys.

Your job is to write a program that takes flawed public keys and determines the corresponding private keys. For the purposes of this problem, a private key consists of a pair of prime numbers,

2 < K1, K2 < 231

and the corresponding public key consists of the product K1 × K2.

입력

The first line of the input contains an integer value, M (2 ≤ M ≤ 100). M is the number of input lines that follow. Each of the M lines contains a single “public key." Each public key is the product of exactly two prime numbers and will fit in a 32-bit unsigned integer.

출력

The output lines produced by your program should contain the unique prime factors of the input data values in ascending numeric order, five per line, except for the last line. Output values on the same line are separated by a single space.

예제 입력 1

6
221
391
713
1457
901
299

예제 출력 1

13 17 23 31 47
53

예제 입력 2

2
2143650557
2140117121

예제 출력 2

32717 65413 65521