Tí có ~n~ cái kẹo và muốn chia hết cho một số em nhỏ. Không được chia tất cả kẹo cho đúng một em. Những em nhận kẹo phải nhận số kẹo bằng nhau.

Yêu cầu

Tìm số kẹo nhiều nhất mà một em có thể nhận.

Input

Một dòng chứa số nguyên ~n~ ~(2 \le n \le 10^9)~.

Output

In ra số kẹo nhiều nhất mà một em có thể nhận.

Subtask

• 80% số điểm: ~2 \le n \le 10^6~.
• 20% số điểm: ~10^6 < n \le 10^9~.

Ví dụ

6

3