Trong các số tự nhiên lừ 1 đến \(N\), số tự nhiên được gọi là số giàu có nhất nêu nó có tổng các ước lớn nhất trong các số này.

Ví du: Số \(12\) là số giàu có nhất trong các số tự nhiên từ 1 đến 15. (Tổng ước của \(12\) là \(1+2+3+4+6+12 = 28\)).

Yêu cầu: Hãy xác định số giàu có nhất trong các số tự nhiên từ 1 đến \(N\).

Dữ liệu

• Nhập từ bàn phím một số tự nhiên \(N\ (0 < N < 10^6)\)

Kết quả

• In ra màn hình số giàu có nhất trong các số tự nhiên từ 1 đến \(N\).

Chú ý: Nếu kết quả có nhiều hơn một số thì in ra sổ nhỏ nhất trong các số đó.

Input

15

Output

12

Giới hạn

• Có 80% test ứng với \(N < 10^5\);
• Có 20% test ứng với \(10^5 < N < 10^6\).

Nguồn: THTB - Cấp TP 2021.