No testdata at current.

Background

拆了他！

Description

定义一个正整数n的拆分是：把它拆成若干个正整数相乘的积。如[2,3,3]、[1,1,1,2,9]，[18]都是正整数18正确的拆分，而[10,4,4]、[1,8]都不是正整数18正确的拆分。定义一个拆分的价值是所有数字加起来的和。如[2,3,3]的价值是8，[1,1,1,2,9]的价值是14。现在，土拨鼠博博给了你一个正整数k，请你告诉博博，在正整数k所有正确的拆分里，价值最小的一个拆分，它的价值是多少。

Format

Input

k

Output

在正整数k所有正确的拆分里，价值最小的一个拆分，它的价值是多少

Samples

18

8

29

29

Limitation

可以证明，18价值最小的拆分是[2,3,3]；可以证明，29价值最小的拆分是[29]；$1≤k≤10^{12}$

1s, 1024KiB for each test case.