Smallest Divisor Greater Than One

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given n≥2, find the smallest positive divisor of n greater than one. For a prime, the answer is n itself.

Input

One integer n.

Output

Print the smallest divisor of n greater than one.

Subtasks

• Subtask 1 (20%): 2 ≤ n ≤ 100.
• Subtask 2 (30%): 2 ≤ n ≤ 100000.
• Subtask 3 (50%): 2 ≤ n ≤ 1000000000.

Examples

Example 1

Input

21

Output

3

Explanation

Twenty-one is not divisible by 2, but is by 3.

Example 2

Input

49

Output

7

Explanation

Seven is the smallest divisor above one.

Example 3

Input

13

Output

13

Explanation

Thirteen has no proper divisor greater than one.