300685: CF130F. Prime factorization

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Prime factorizationtime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

You are given an integer n. Output its prime factorization.

If n = a1b1a2b2 ... akbk, where ak are prime numbers, the output of your program should look as follows: a1 a1 ... a1 a2 a2 ... a2 ... ak ak ... ak, where factors are ordered in non-decreasing order, and each factor ai is printed bi times.

Input

The only line of input contains an integer n (2 ≤ n ≤ 250).

Output

Output the prime factorization of n, as described above.

ExamplesInput
245
Output
5 7 7 
Input
13
Output
13 

Input

加入题单

上一题 下一题 算法标签: