切蛋糕

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

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

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