Домножить до куба

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

Ответ может быть очень большим — до $10^{24}$.

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

Одно число.

Число является полным кубом ровно тогда, когда все показатели в его разложении делятся на три. Ответ может оказаться очень большим — в Python это не мешает.