Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

`Copy All`

: You can copy all the characters present on the notepad (partial copy is not allowed).`Paste`

: You can paste the characters which are copied**last time**.

Given a number `n`

. You have to get **exactly** `n`

‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get `n`

‘A’.

**Example 1:**

Input:3Output:3Explanation:Intitally, we have one character 'A'. In step 1, we useCopy Alloperation. In step 2, we usePasteoperation to get 'AA'. In step 3, we usePasteoperation to get 'AAA'.

**Note:**

- The
`n`

will be in the range [1, 1000].

```
from functools import lru_cache
class Solution:
def minSteps(self, n: int) -> int:
# @lru_cache(None)
# def operation(notepad, current):
# def operation(notepad, current):
# if len(current) <= n:
# if len(current) == n:
# return 0
# # no notepad
# t1 = (operation(current, current) if not notepad else 0x7777777) + 1
# # paste from notepad
# t2 = (operation(notepad, current + notepad) if notepad else 0x7777777) + 1
# # update notepad
# t3 = (operation(current, current) if notepad and notepad != current else 0x7777777) + 1
# return min(t1, t2, t3)
# else:
# return 0x7777777
# result = operation(0, "A")
# return result
if n == 1:
return 0
for i in range(2,n+1):
if n % i == 0:
return i + self.minSteps(int(n/i))
```