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