Problem Description

Little R is a cute girl, and she likes prime factorization.

She has a positive integer $x$. In each operation, you may choose $p_1, \alpha_1, p_2, \alpha_2$ such that $p_1, p_2$ are two different primes and $\alpha_1, \alpha_2$ are positive integers. If $x$ is divisible by $p_1^{\alpha_1} p_2^{\alpha_2}$, then divide $x$ by $p_1^{\alpha_1} p_2^{\alpha_2}$; otherwise, the operation is invalid.

Please find the minimum possible value of $x$ that can be obtained after performing the operation some number of times.

Input Format

One line containing one integer $x$.

Output Format

Output one integer, the minimum possible $x$ that can be obtained.

9

9

120

1

2310

2

Hint

Explanation for Sample $1$

No valid operation can be performed.

Explanation for Sample $2$

You can perform the following two operations:

• Let $p_1 = 2, \alpha_1 = 1, p_2 = 3, \alpha_2 = 1$. Divide $x$ by $p_1^{\alpha_1} p_2^{\alpha_2} = 2^1 3^1 = 6$, obtaining $x = 20$.
• Let $p_1 = 2, \alpha_1 = 2, p_2 = 5, \alpha_2 = 1$. Divide $x$ by $p_1^{\alpha_1} p_2^{\alpha_2} = 2^2 5^1 = 20$, obtaining $x = 1$.

Constraints

This problem uses bundled tests. You can only get the corresponding score if you pass all test points in a subtask and all subtasks it depends on.

For all data: $2 \le x \le 10^9$.

• Subtask 1 ($10$ points): $x \le 10$.
• Subtask 2 ($20$ points): $x$ is a "square-free number"$^\dagger$.
• Subtask 3 ($20$ points): $x$ is a positive integer power of a prime.
• Subtask 4 ($20$ points): $x \le 10^5$. Depends on Subtask 1.
• Subtask 5 ($30$ points): No special constraints. Depends on Subtasks 1, 2, 3, and 4.

$\dagger$ A number $x$ is called a "square-free number" if and only if there does not exist an integer $k > 1$ such that $x$ is divisible by $k^2$.

Translated by ChatGPT 5