Nhân ngày sinh nhật, Bình mời bạn bè đến dự tiệc và tổ chức một trò chơi như sau:
Bình có một dãy gồm n ô được đánh số thứ tự từ 1 đến n, anh đặt n chiếc bánh sinh nhật vào mỗi ô một chiếc. Trong đó chiếc bánh sinh nhật ở ô số 1 được đặt lên đó một quả cherry thơm ngon.
Bắt đầu từ vị trí ô thứ 2, Bình di chuyển sang vị trí ô thứ n, khi di chuyển đến ô thứ k anh sẽ tính toán để tìm được d là ước lớn nhất của k và khác k, sau đó thực hiện hoán đổi vị trí của hai chiếc bánh sinh nhật ở ô thứ k và ô thứ d.
Sau khi kết thúc công việc của mình tại ô thứ n, Bình đố bạn bè của mình tìm vị trí của chiếc bánh sinh nhật có đặt quả cherry lên đó, ai tìm ra được vị trí đó thì sẽ được một phần quà vô cùng ý nghĩa từ Bình.
Em hãy giúp bạn bè của Bình nhé.

Input

-BIRTHDAY.INP: một dòng duy nhất chứa số nguyên dương n (1≤n≤10^14).

Output

• BIRTHDAY.OUT: một số nguyên là vị trí của chiếc bánh sinh nhật có quả cherry.

4

4

5

4

Giới hạn:

Subtask 1: 40% số điểm 1≤n ≤ 1000
Subtask 2: 30% số điểm 1000<n≤10^6
Subtask 2: 20% số điểm còn lại không có ràng buộc gì