Головний режисер шоу хоче, щоб участники шоу могли шикуватись у різну кількість колон рівно n способами. Причому при довільному шикуванні кількість людей у кожній з колон повинна бути однаковою.
Потрібно повідомити режисеру, яка мінімальна кількість людей m йому для цього буде потрібна. Так, при n = 3 потрібно запросити усього m = 4 человік, які можуть вишуватись у 1, 2 і 4 колони. Якщо ж при деякому n для шоу потрібно більше 10^9 человік, то режисеру можна повідомити, що потрібне число людей зібрати неможливо.
Єдиний рядок вхідного файла містить натуральне число n ≤ 1000.
Якщо для заданого n мінімальне число людей m для шоу не перевищує 10^9, то виведіть у вихідний файл це число m, у протилежному випадку – виведіть число 0.