Đề bài

Trên hành tinh SaiYan tồn tại một loại cổ thạch kỳ bí mang tên Thạch Cộng Hưởng.
Mỗi viên thạch có một chỉ số yêu cầu năng lượng là số nguyên dương \(N\).

Khi kích hoạt, viên đá tự tạo ra một mức năng lượng phụ thuộc vào trạng thái cộng hưởng của nó. Ở trạng thái cộng hưởng cấp \(X\), năng lượng viên đá tạo ra là (\(X^X\)).

Theo quy luật cổ xưa, viên đá chỉ kích hoạt thành công nếu năng lượng nó tự sinh ra tương thích hoàn toàn với chỉ số yêu cầu, tức là:

• \(N\) phải chia hết bởi (\(X^X\)), hay nói cách khác: (\(X^X\)) chia hết cho \(N\).

Tuy nhiên, viên đá luôn muốn kích hoạt ở cấp thấp nhất có thể, vì cộng hưởng quá mức sẽ gây tổn hại cho cấu trúc tinh thể.

Hãy xác định giá trị X nhỏ nhất sao cho năng lượng cộng hưởng (\(X^X\)) chia hết cho \(N\).

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương \(N\).

Dữ liệu ra

• Một số nguyên duy nhất: giá trị nhỏ nhất của X sao cho (\(X^X\)) chia hết cho \(N\).

Ràng buộc

• (\(2 \le N \le 10^9\))
• Subtask 1: (\(N \le 15\))
• Subtask 2: (\(N \le 10^6\))
• Subtask 3: (\(N \le 10^9\))

Sample Input 1

9

Sample Output 1

3

Sample Input 2

6

Sample Output 2

6

Giải thích

• Với \(N = 9\), cấp cộng hưởng thấp nhất để (\(X^X\)) chia hết cho 9 là \(X = 3\).
• Với \(N = 6\), cấp cộng hưởng thấp nhất để (\(X^X\)) chia hết cho 6 là \(X = 6\).