Ở hành tinh SaiYan có quá nhiều thứ mới lạ, Hưng quyết định phải đi đến một lớp học thêm để có thể biết thêm nhiều thông tin về hành tinh này. Thật may là lúc này, Mr Toàn khai trương trung tâm dạy học với vô vàn ưu đãi, chính vì vậy, Hưng đã quyết định đăng kí ngay và luôn vào lớp học của thầy. Ngày đầu tiên đến, đập vào mắt Hưng là một biển người đông ngút trời và Mr Toàn đang phát biểu nhân ngày trung tâm khai trương. Sau khi phát biểu xong, Mr Toàn lại cảm thấy số lượng học sinh là quá đông ngược lại số lượng phòng học lại mới chỉ có N. Chính vì vậy, Thầy quyết định sẽ chỉ lấy X học sinh sao cho \(X^X\) chia hết cho \(N\). Nhưng nếu chỉ có thế, số học sinh có thể là vô hạn, nên thầy quyết định sẽ chọn X nhỏ nhất sao cho \(X^X\) chia hết cho N. Đúng lúc này, Thầy lại có việc bận nên Thầy đã nhờ Hưng (Một người khá nổi tiếng tại hành tinh SaiYan và cũng đăng kí lớp học của thầy) giúp thầy để đổi lại một suất học miễn phí toàn phần. Hưng liền nhận lời nhưng kẻ thù không đội trời chung - Nhân Thiện và phù thuỷ Vương Lượng cũng đến đăng kí học. Vì biết nếu Hưng giúp thầy sẽ nhận được một suất học miễn phí nên họ ra sức quấy phá Hưng khiến Hưng không thể tập trung hoàn thành nhiệm vụ. Các bạn hãy giúp Hưng nhé !!!

Dữ liệu :

Một dòng gồm số nguyên dương \(N\) là số lớp học tại trung tâm \((2 \leq N \leq 10^9)\).

Kết quả :

Một dòng duy nhất là số \(X\) nhỏ nhất sao cho \(X^X\) chia hết cho \(N*\).

Ràng buộc:

• Sub1: \(N \leq 15\).
• Sub2: \(N \leq 10^6\).
• Sub3: \(N \leq 10^9\).

Dữ liệu vào

9

Dữ liệu ra

3

Dữ liệu vào

6

Dữ liệu ra

6