473. Droid formation

Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

A long time ago (but somehow in the future), in a Galaxy Far Far Away...

— Your majesty, Jedi detachment almost finished to mine our new Death Cube! New battle droids are unable to restrain them! What to do!?

— Rest assured! What is the strength of every troop of droids?

— 12 droids, your majesty!

— Fools! I told you that a troop should have 4 variants of evolution but troop of 12 droids has 6! This perverts threads of the Power — and infeeds Jedis! Regroup the army — and Jedis will lose!

— Yes sir!

Number of variants of evolution of a troop of droids is the number of ways to draw it up in rows so that every row has the same number of droids. For example, a troop of 12 droids can be arranged in 1 row of 12 droids, 2 rows of 6 droids, 3 rows of 4 droids, 4 rows of 3 droids, 6 rows of 2 droids and 12 rows consisting of 1 droid each. So, as the Emperor noticed, there are 6 variants of evolution for this troop of droids.

You problem is more general — given the number K of favorable variants of evolution, find the smallest positive size of a troop of droids N which has this very number of variants of evolution.

Input file contains only number K from the problem statement (1 ≤ K ≤ 105).

Write to the output file the required number N. If there is no such number, write to the output file number 0 instead.

sample input
sample output