Problem Description

Xiao R is a lovely girl who enjoys factoring numbers into primes.

She has a positive integer \( x \). In each operation, she can choose \( p_1, \alpha_1, p_2, \alpha_2 \) such that \( p_1 \) and \( p_2 \) are two different primes and \( \alpha_1 \) and \( \alpha_2 \) are positive integers. If \( x \) is an integer multiple of \( p_1^{\alpha_1} p_2^{\alpha_2} \), then \( x \) is divided by \( p_1^{\alpha_1} p_2^{\alpha_2} \); otherwise, the operation is invalid.

Please determine the smallest \( x \) that can be obtained through several operations.

Input Format

A single line containing an integer \( x \).

Output Format

An integer representing the smallest \( x \) that can be obtained.

Sample Input and Output

Sample Input #1

9

Sample Output #1

9

Sample Input #2

120

Sample Output #2

1

Sample Input #3

2310

Sample Output #3

2

Notes

Sample 1 Explanation

No valid operations can be performed.

Sample 2 Explanation

The following two operations can be performed:

• 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 \), resulting in \( 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 \), resulting in \( x = 1 \).

Data Range

This problem is bundled. You must pass all test cases in the subtask and all dependent subtasks to receive the corresponding score.

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 integer"$^\dagger$.
• Subtask 3 (20 points): \( x \) is a power of a prime number.
• Subtask 4 (20 points): \( x \le 10^5 \). Depends on Subtask 1.
• Subtask 5 (30 points): No special restrictions. Depends on Subtasks 1, 2, 3, and 4.

$^\dagger$ An integer \( x \) is called a "square-free integer" if and only if there is no integer \( k \) greater than one such that \( x \) is an integer multiple of \( k^2 \).

见题面 Input 部分

见题面 Output 部分