Prime Factorisation

Medium#math #primes· solved by 0 · time limit 2.0 s

Write $n$ as a product of primes in increasing order, using p^k when a prime appears more than once, joined by x. For example $360 =$ 2^3 x 3^2 x 5.

Input

A single integer $n \ge 2$ .

Output

The factorisation.

Constraints

$2 \le n \le 10^{12}$

Sample 1

Input

Output

2^3 x 3^2 x 5

Sample 2

Input

Output