Một số nguyên dương \(x\) được gọi là số đẹp nếu như tất cả các ước số của nó không phải là số chính phương lớn hơn \(1\).

Ví dụ: \(5\) là số đẹp vì \(2\) ước số \(1\) và \(5\) của nó không phải số chính phương lớn hơn \(1\), trong khi đó \(12\) không phải là số đẹp vì nó có ước số \(4\) là một số chính phương lớn hơn \(1\).

Cho một số nguyên dương \(n\), hãy tìm ước số \(d\) lớn nhất của \(n\) sao cho \(d\) là một số đẹp.

Input

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

Output

• Ghi ra một số nguyên là ước số \(d\) lớn nhất của \(n\) sao cho \(d\) là một số đẹp. Nếu không tồn tại ước số nào của \(n\) là số đẹp thì in ra \(-1\).

Example

10

10

12

6

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{12}\).