题目描述

你有一块非常长且薄的蛋糕。我们可以认为它是一维的，长度为n。

今天是你的生日，你有不少朋友要来你的寝室开party。

在你朋友到来前，你想要把蛋糕切好成若干块。

当你的朋友到来时，你会用以下规则来分配蛋糕。

从蛋糕的左端开始，你给你的第一位朋友若干块连续的蛋糕，接下来你给第二位朋友之后的若干块连续的蛋糕，以此类推。

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

不同的朋友拿到的蛋糕块数可能不同，但量必须相同。

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

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

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

<p>

</p> <p> 下面解释第一组样例数据。 </p> 由于蛋糕长度为6。所以朋友个数x可能为1个，2个或者3个。

我们可以将蛋糕切成2,1,1,2，这样的4份。

如果只有1个朋友，直接全部给他。

如果有2个朋友，我们将第一块和第二块给第一个朋友，第三块和第四块给第二个朋友。

如果有3个朋友，我们将第一块给第一个朋友，第二和第三块给第二个朋友，第四块给第三个朋友。

以上的切法是最少的。

所以答案为4。

输入格式

多组输入数据

每组数据第一个数为n

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

</p>

输出格式

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

样例

样例 1

输入 # 1

6
3
15

输出 # 1

4
1
7