Largest Proper Divisor

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given integer $n\ge2$, print its largest positive divisor strictly less than $n$. The divisor 1 is valid, including for a prime $n$.

Input

One integer $n$ with $2\le n\le10^6$.

Output

Print the largest positive divisor smaller than $n$.

Subtasks

• Subtask 1 (20%): $2\le n\le 50$.

• Subtask 2 (30%): $2\le n\le 10000$.

• Subtask 3 (50%): $2\le n\le 1000000$.

Examples

Example 1

Input:

12

Output:

6

Explanation:

The largest positive divisor of 12 strictly below 12 is 6.

Example 2

Input:

13

Output:

1

Explanation:

The largest positive divisor of 13 strictly below 13 is 1.