FACTCG2 - Medium Factorization

The task in this problem is to write a number in a multiplication of prime numbers separated by “ x ”. You need to put the number 1 in this multiplication.

Input

The input consists of several lines.

Each line consists of one integer N (1 <= N <= 10^7) .

Output

For each line you need to output the factorization separated by “ x ” and including 1.

Sample

Input
1
2
4
8

Output
1
1 x 2
1 x 2 x 2
1 x 2 x 2 x 2

Added by:Phyllipe Medeiros
Date:2012-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2012-02-27 03:07:21 Alex Anderson
... I posted this on the other problem, but again, this already exists: See FACT0 FACT1 FACT2
2012-02-27 02:54:13 Clément Sommelet
To get accepted, I had to put the factors in ascending order and to use " x " as a separator, not " x".
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.