题目描述

信息学社团开展文本编辑主题闯关赛，小珅和小泽拿到了一台操作受限的简易记事本编辑器，编辑器仅支持全局复制与粘贴两类操作，初始编辑区域里仅存在单个字符A。两人需要用最少操作次数拼出指定数量的A字符序列，以此拿到闯关积分，请你帮他们设计最优操作方案并统计最小操作步数。 编辑器仅能执行下面两种操作：

1. Copy All（全局全量复制）：一次性复制记事本内当前存在的全部字符，不支持选中局部片段进行部分复制；
2. Paste（粘贴操作）：把上一次Copy All缓存的全部字符追加到记事本末尾。

给定正整数$n$，要求通过若干次上述操作，让记事本里恰好出现$n$个A字符，请求出达成目标需要的最少操作总次数。

输入格式

输入一行一个正整数$n$。

输出格式

输出一行一个非负整数，代表凑出恰好$n$个A所需的最小操作次数。

输入输出样例

3

3

1

0

说明/提示

样例1详细解释

初始记事本内已有1个A： 第1步执行Copy All，把当前1个A存入剪贴板； 第2步执行Paste，记事本字符变为AA； 第3步执行Paste，记事本字符变为AAA； 全程一共3次操作，是能凑出3个A的最优方案。

数据范围

$1 \le n \le 1000$

2

2