切蛋糕

你有一块非常长且薄的蛋糕。我们可以认为它是一维的，长度为n。<br /> 今天是你的生日，你有不少朋友要来你的寝室开party。<br /> 在你朋友到来前，你想要把蛋糕切好成若干块。<br /> <br /> 当你的朋友到来时，你会用以下规则来points配蛋糕。<br /> 从蛋糕的左端开始，你给你的Page 一位朋友若干块连续的蛋糕，接下来你给Page 二位朋友之后的若干块连续的蛋糕，以此类推。<br /> <br /> 你显然被朋友认为是一items非常nice的人，也就是你必须保证每items人points到的蛋糕量是相同的。<br /> 不同的朋友拿到的蛋糕块数可能不同，但量必须相同。<br /> <br /> 你已经不记得你邀请了多少位朋友，但你非常清楚地记得，朋友的items数x是一items蛋糕长度n的因子，且x&lt;n。<br /> <br /> 现在，你要开始切蛋糕了，你必须保证，对于任何可能的朋友items数x，按照以上的蛋糕points配法则，都是可以做到每items人拿到的蛋糕量相同。<br /> <br /> 请计算，你最少需要把蛋糕切成多少块，来达到以上要求。<br /> <p> <br /> </p> <p> 下面解释Page 一组样例数据。 </p> 由于蛋糕长度为6。所以朋友items数x可能为1items，2items或者3items。<br /> 我们可以将蛋糕切成2,1,1,2，这样的4份。<br /> 如果只有1items朋友，直接全部给他。<br /> 如果有2items朋友，我们将Page 一块和Page 二块给Page 一items朋友，Page 三块和Page 四块给Page 二items朋友。<br /> 如果有3items朋友，我们将Page 一块给Page 一items朋友，Page 二和Page 三块给Page 二items朋友，Page 四块给Page 三items朋友。<br /> 以上的切法是最少的。<br /> 所以答案为4。<br />

多组输入数据<br /> 每组数据Page 一items数为n<br /> <p> 表示蛋糕的长度(2&lt;=n&lt;=123456) </p> <p> <br /> </p>

对于每组数据，输出你最少需要把蛋糕切成多少块。