Smallest Prime Factor

Given a positive integer \( n \) which can be factorized as \( n = p_1 \times p_2 \times \dots \times p_k \) where each \( p_i \) is a prime number and \( p_i \leq p_{i+1} \) for \( 1 \leq i < k \), your task is to compute the smallest prime factor \( p_1 \) of \( n \).

Examples:

• \( 36 = 2 \times 2 \times 3 \times 3 \), smallest prime factor is \( 2 \).
• \( 49 = 7 \times 7 \), smallest prime factor is \( 7 \).
• \( 89 = 89 \), smallest prime factor is \( 89 \).
• \( 967217 = 37 \times 26141 \), smallest prime factor is \( 37 \).

inputFormat

The input consists of a single line containing a positive integer \( n \).

outputFormat

Output the smallest prime factor of \( n \).

sample

36

2