2 Keys Keyboard

A text editor initially contains one A, and the clipboard is empty. You may copy the entire current text to the clipboard, replacing its previous contents, or paste the clipboard at the end of the text. Each copy or paste costs one operation. Return the fewest operations needed to end with exactly n copies of A.

Example 1:

Input: n = 4

Output: 4

Explanation: Copy A, paste to get AA, copy AA, then paste to get AAAA. These four operations are optimal.

Example 2:

Input: n = 6

Output: 5

Explanation: Copy A and paste to get AA. Copy AA, then paste twice to get AAAAAA. This uses five operations, the minimum.

Example 3:

Input: n = 1

Output: 0

Explanation: The editor already contains exactly one A, so no operation is needed.

Constraints:

• 1 <= n <= 1000