You start with a text editor that initially contains a single character 'A'. You can perform only the following operations.

Copy All: copy the entire current content to the clipboard.
Paste: append the clipboard content to the current content.

Given an integer n, return the minimum number of operations needed to end with exactly n characters 'A' in the editor.

Constraints:

• $1 \leq$ n $\leq 10^3$

Input: n = 2-int
Output: 2-int
Explanation: Starting with "A", Copy All puts "A" on the clipboard and Paste gives "AA" (2 characters), so the minimum number of operations is 2.

Input: n = 7-int
Output: 7-int
Explanation: Since 7 is prime, the only way is to Copy All once and then Paste "A" 6 times, for a total of 1 + 6 = 7 operations.

Input: n = 16-int
Output: 8-int
Explanation: Using the factorization 16 = 2 × 2 × 2 × 2, each “multiply by 2” costs 2 operations (Copy All + Paste), taking "A" to 2, 4, 8, and then 16 characters, for a total of 2 + 2 + 2 + 2 = 8 operations.

Input: n = 997-int
Output: 997-int
Explanation: 997 is prime, so it cannot be reached faster via intermediate multiplication steps, and the minimum number of operations is 997 (Copy All once, then Paste 996 times).

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.