Trong chương trình toán 6 nhắc đến việc phân tích một số ra thành tích các thừa số nguyên tố. Xét dạng phân tích ra thừa số nguyên tố của số N ≥ 2:

N = P₁^a1 P₂^a2 P₃^a3 ... P_k^ak

Người ta gọi số S là tích của các thừa số nguyên tố khác nhau trong phân tích thừa số nguyên tố của N.

Ví dụ: N = 12, khi phân tích thừa số nguyên tố của N ta có N = 2² 3 nên S = 2 3 = 6.

Yêu cầu:

Cho số nguyên dương M, tìm số N ≤ M mà có S lớn nhất.

Input:

Ghi số nguyên dương N (2 ≤ M ≤ 10⁹)

Output:

Ghi kết quả bài toán

Giới hạn:

- 80% test thỏa 2 ≤ M ≤ 2 * 10⁵

- 20% test thỏa 10⁵ < M ≤ 10⁹.

Ví dụ:

Input

28

Output

26