You will given an integer number N. Find the prime factors of this number.

Input

The input consists of several lines.

Each line consists of one integer N (2 ≤ N ≤ 10⁷)

Output

In each line you need to print the factors of N separated by " x ".

Example

Input:
2
8
6
Output:
2 = 2
8 = 2 x 2 x 2
6 = 2 x 3