2 Keys Keyboard

Imagine a very simple text editor that supports exactly two operations:

• Copy All : Copy the entire current screen content into the clipboard. (Partial copy is not allowed.)
• Paste : Paste the content from the clipboard onto the screen.

Initially, the screen contains a single character A. Your goal is to display exactly $N$ characters A on the screen using the minimum number of operations possible. Find the minimum number of operations required when acting optimally.

The first line contains a single integer $N$, representing the number of characters A to be displayed. $(1 \leq N \leq 1\,000\,000)$

Print a single integer: the minimum number of operations required.