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⁷) .

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