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^5) .

Output

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

Sample Input

1

2

4

8

Sample Output

1
1 x 2
1 x 2 x 2
1 x 2 x 2 x 2