Домножить до квадрата

Найдите наименьшее натуральное $k$, при котором произведение $n \cdot k$ является полным квадратом.

Одно целое число $n$ от $1$ до $10^{12}$.

Одно число.

Число является полным квадратом ровно тогда, когда в его разложении все показатели чётны. Значит домножить надо на те простые, что встречаются нечётное число раз.