Главный режиссер шоу, посвященного открытию ACM Programming Contest, хочет, чтобы участники шоу могли выстраиваться в различное число колонн ровно N способами. Причем при любом перестроении количество людей в каждой из колонн должно быть одинаковым. Требуется сообщить режиссеру, какое минимальное число М человек ему для этого понадобится. Так, при N = 3 потребуется пригласить всего М = 4 человек, которые могут выстроиться в 1, 2 и 4 колонны. Если же при некотором N для шоу потребуется более 10 ⁹ человек, то режиссеру можно сообщить, что подходящее число людей собрать невозможно.