Given odd integer n > 2 compute its least prime divisor.

Input

Each line of input contains one random odd integer number 2 < n < 10⁸ (100 000 000). Input terminates with 0 (zero). There will be two input files.

Output

For each n print its least prime divisor on new line.

Example

Input:
3
9
11
15
49
0

Output:
3
3
11
3
7