题目描述

小 Z 现在要结一个单价为 $n$ 的商品，她可以分无数次付款，每次付款的钱数为付款钱数的最大因子，她想问你她最少需要付多少钱？

换句话说：

给定一个尾款金额 $n$ 。
小 Z 可以无限次支付尾款，每一次支付的金额规则是：

当前付款金额的 最大因数（不包含它本身）。

目标是：
通过合理拆分支付顺序，使得最终支付的总金额最小。

输入格式

一行一个整数 $n$ 代表要结的尾款金额。

输出格式

最少需要付多少钱。

样例

3

1

4

2

数据范围

$2 \leq n \leq 2\times 10^9$。