Sau nhiều năm cày cuốc, Chính đã mua được cho mình một căn biệt thự to bự. Hôm nay là ngày họp mặt đại gia đình, họ hàng; vì biệt thự của Chính vô cùng rộng rãi, thoáng mát và thư giãn nên mọi người đã chốt địa điểm họp ở đó. Nhưng vì chính quá béo nên đã ngủ quên tới chiều, trong lúc mọi người đang đứng chờ ở trước cổng biệt thự. Quá bức xúc, mọi người quyết định tự mình tìm cách mở cổng thay vì chờ Chính.

Cổng biệt thự bị khóa bằng một loại ổ khóa đặc biệt, mật khẩu là một số nguyên dương \(x\). Trên cổng vô tình có một tờ giấy gợi ý ghi: \(F(x) = a\) với \(a\) là một số nguyên dương cho trước. Trên tờ giấy đó cũng có định nghĩa \(F(x)\) là tổng các ước số nguyên dương \(k\) của \(x\) thỏa mãn điều kiện \(k\) và \(\frac{x}{k}\) nguyên tố cùng nhau. Bạn hãy giúp người thân của Chính xác định được mật khẩu \(x\) để mở khóa cổng biệt thự, do có thể có nhiều hơn một giá trị thỏa mãn \(F(x) = a\), mật khẩu chính là giá trị \(x\) nhỏ nhất.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(a\) (\(a \le 10^{10}\)).
• Dữ liệu vào đảm bảo luôn tồn tại mật khẩu \(x\).

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán.

Example

3

2

12

6

Scoring

• \(30\%\) số điểm có \(a \le 100\).
• \(30\%\) số điểm khác có \(a \le 10^4\).
• \(40\%\) số điểm còn lại có \(a \le 10^{10}\).