Cho số nguyên dương \(n\). Hãy phân tích \(n\) thành tích các thừa số nguyên tố.

Kết quả in ra dưới dạng \(p_1^{k_1} \times p_2^{k_2} \times \dots \times p_m^{k_m}\) với \(p_i\) là số nguyên tố tăng dần, \(k_i\) là số mũ tương ứng.

Gợi ý: Chia \(n\) cho \(2\) đến hết, sau đó chia cho các số lẻ từ \(3\) đến \(\sqrt{n}\). Nếu \(n > 1\) sau vòng lặp thì \(n\) là một thừa số nguyên tố lớn.

Input

Một dòng duy nhất chứa số \(n\) (\(2 \le n \le 10^{12}\)).

Output

In ra kết quả phân tích. Các thừa số cách nhau bởi dấu × (dấu nhân), mỗi thừa số có dạng p^k nếu \(k > 1\) hoặc chỉ p nếu \(k = 1\).

Example

60

Output:

2^2 × 3 × 5

100

Output:

2^2 × 5^2