你有一块非常长且薄的蛋糕。我们可以认为它是一维的，长度为n。
今天是你的生日，你有不少朋友要来你的寝室开party。
在你朋友到来前，你想要把蛋糕切好成若干块。

当你的朋友到来时，你会用以下规则来分配蛋糕。
从蛋糕的左端开始，你给你的第一位朋友若干块连续的蛋糕，接下来你给第二位朋友之后的若干块连续的蛋糕，以此类推。

你显然被朋友认为是一个非常nice的人，也就是你必须保证每个人分到的蛋糕量是相同的。
不同的朋友拿到的蛋糕块数可能不同，但量必须相同。

你已经不记得你邀请了多少位朋友，但你非常清楚地记得，朋友的个数x是一个蛋糕长度n的因子，且x<n。

现在，你要开始切蛋糕了，你必须保证，对于任何可能的朋友个数x，按照以上的蛋糕分配法则，都是可以做到每个人拿到的蛋糕量相同。

请计算，你最少需要把蛋糕切成多少块，来达到以上要求。

<br />

下面解释第一组样例数据。

多组输入数据
每组数据第一个数为n

表示蛋糕的长度(2<=n<=123456)

<br />

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