Prime Factorization

Halloway Packaging ships each production run as one batch, and the floor supervisor needs to know which box sizes will divide a batch evenly with nothing left over. Every workable size is built out of the batch size's prime building blocks, so the planning screen lists those blocks first. A run of 12 breaks down into 2, 2 and 3 -- and the repeated 2 matters, because a box of 4 is only on the table if there are two of them to draw on.

Task: Print the prime factors of the batch size in increasing order, writing a factor out as many times as it divides in.

Input

A single line holding one integer n, with 2 <= n <= 1,000,000,000.

Output

One line holding the prime factors in increasing order, separated by single spaces, repeats written out in full. Multiplying the printed numbers together has to give back n.

Example:

Input:
12

Output:
2 2 3