Pharaoh hEx ruled a square country many thousands of years ago. Like all previous pharaohs, the main goal of his life was the construction of a magnificent pyramid. hEx was vain and very eager to out-perform its predecessors. How? By building a higher pyramid, of course!

The fact is that the pyramids of all previous pharaohs were of the same size, and there were serious reasons for this. For the construction of the pyramid it is necessary to lay a solid foundation of extremely hard granite. Granite of the required quality was mined at the only quarry. It was in the form of absolutely identical cubes. The transportation of these cubes was not a simple matter. Exactly $$$n$$$ ($$$1 \leq n \leq 10^9$$$) of such granite blocks were delivered from the quarry in one supply.

Since the base of the pyramid must be a perfect square, all previous pharaohs simply performed $$$n$$$ deliveries and built pyramids on the base of $$$n^2$$$ blocks. Pharaoh hEx wants to build his pyramid on a larger foundation. He has already planned $$$n$$$ required deliveries of $$$n$$$ cubic stones, but additional shipments will be needed to enlarge the foundation. Pharaoh wants to make the minimum possible number of over-scheduled transportations $$$p$$$. He also requires that the volume of single shipment does not decrease (all the same $$$n$$$ blocks) and that after laying the square foundation there won't be extra blocks left.

Let's look at an example. Let $$$n = 4$$$, then for the $$$4$$$ scheduled transportations $$$16$$$ blocks will be received, of which a $$$4\times4$$$ foundation can be laid. If we add one over-planned transportation ($$$p = 1$$$), then there will be $$$20$$$ stone cubes, from which it will not be possible to lay out a square, which means that $$$p$$$ cannot be one. Similarly, for $$$p = 2, 3, 4$$$ we get $$$24$$$, $$$28$$$, and $$$32$$$ cubes, which also does not allow us to lay them in the form of a square without excess. Finally, with the $$$5$$$ over-planned deliveries, we get $$$36$$$ cubic blocks, from which you can build a $$$6\times 6$$$ foundation. So for $$$n = 4$$$ we get $$$p = 5$$$.