Cho trước số nguyên dương \(n\ (0 < n \leq \ 10^{6})\).

Yêu cầu: Tìm số nguyên dương \(k\) nhỏ nhất sao cho tích của \(k\) và \(n\) là một số chính phương.

Dữ liệu vào:

+ Số nguyên dương \(n\).

Dữ liệu ra:

+ Ghi số nguyên \(k\) tìm được.

Ví dụ:

Input	Output		Input	Output
3	3		18	2