ABBYY 的 Smart Beaver 决定休息一天。但一整天无所事事太无聊了,他决定玩鹅卵石游戏。最初,海狸有 n 个卵石。他将它们排成相等的行,每行有 b 个卵石(a > 1)。请注意,海狸必须使用他拥有的所有卵石,即。 e. n = a·b。
10颗鹅卵石排成两行,每行有5颗鹅卵石
一旦智能海狸排列好鹅卵石,他就会收回任何由此产生的行(即 b 颗鹅卵石)并丢弃所有其他鹅卵石。然后他再次排列所有的鹅卵石(可能选择 a 和 b 的其他值)并收回一行,依此类推。游戏一直持续到某个时刻,海狸最终得到了一颗鹅卵石。
游戏过程可以表示为整数 c1, ..., ck 的有限序列,其中:
- c1 = n
- ci + 1 是 Beaver 在第 i 次移动后最终得到的卵石数量,即 ci 卵石经过某种排列后排成一行的卵石数量 (1 ≤ i < k)。请注意,ci > ci + 1。
- ck = 1
游戏的结果是数字ci的总和。给你n。找出游戏的最大可能结果。
输入
输入的单行包含一个整数 n — 智能海狸拥有的卵石的初始数量。
获得 30 点的输入限制为:
- 2 ≤ n ≤ 50
获得 100 点的输入限制为:
- 2 ≤ n ≤ 109
输出
打印一个数字——游戏的最大可能结果。
示例
输入 #1
10
输出 #1
16
输入 #2
8
输出 #2
15
注意
考虑第一个示例 (c1 = 10)。游戏开发的可能选项有:
- 将卵石排成 10 行,每行一颗卵石。那么c2 = 1,第一步棋结束后游戏结果为11。
- 将鹅卵石排成 5 行,每行两颗鹅卵石。那么c2 = 2,游戏继续。在第二步中,我们有两个鹅卵石,可以以独特的方式排列(请记住,您不能将所有鹅卵石放在同一行!) - 2 行,每行一个鹅卵石。 c3 = 1,游戏以13结束。
- 最后,将卵石排成两行,每行五个卵石。同样的逻辑导致 c2 = 5, c3 = 1,游戏以 16 结束——最大可能的结果。