Фараон hEx правил квадратной страной много тысяч лет назад. Как и у всех предыдущих фараонов, главной целью его жизни, было строительство величественной пирамиды. hEx был тщеславным и очень хотел перещеголять своих предшественников. Как? Конечно же построив большую пирамиду!

Дело в том, что пирамиды всех предыдущих фараонов имели одинаковые размеры, и на это были серьезные причины. Для строительства пирамиды необходимо заложить надежный фундамент из крепкого гранита. Гранит надлежащего качества добывался на единственной каменоломне в виде абсолютно одинаковых кубов. Перевозка этих кубов была непростым делом, и за одну перевозку с каменоломни доставляли ровно $$$n$$$ ($$$1 \leq n \leq 10^9$$$) таких гранитных блоков. Так как основание пирамиды должно быть идеальным квадратом, то все предшествующие фараоны просто совершали $$$n$$$ перевозок и строили пирамиды на основании из $$$n^2$$$ блоков.

Фараон hEx хочет построить свою пирамиду на более крупном фундаменте. Он уже запланировал обязательные $$$n$$$ перевозок по $$$n$$$ кубов, но для увеличения фундамента потребуются дополнительные перевозки. Фараон хочет сделать минимально возможное количество сверхплановых перевозок $$$p$$$. Также он требует, чтобы объем единичной перевозки не сокращался (все те же $$$n$$$ блоков), и чтобы после укладки квадратного фундамента лишних блоков не осталось.

Рассмотрим пример. Пусть $$$n = 4$$$, тогда за $$$4$$$ плановых перевозки будут получены $$$16$$$ блоков, из которых можно уложить фундамент $$$4\times4$$$. Если добавить одну сверхплановую перевозку ($$$p = 1$$$), то будет $$$20$$$ каменных кубов, из которых не получится выложить квадрат, значит $$$p$$$ не может быть единицей. Аналогично, для $$$p = 2, 3, 4$$$ получаем $$$24$$$, $$$28$$$ и $$$32$$$ куба, что также не позволяет уложить их в виде квадрата без остатков. Наконец, при $$$5$$$ сверхплановых поставках получаем $$$36$$$ кубических блоков, из которых можно построить фундамент $$$6\times 6$$$. Значит для $$$n = 4$$$ получим $$$p = 5$$$.