Factor Solitaire

Στο παιχνίδι της πασιέντζας παραγόντων, ξεκινάτε με τον αριθμό ~1~ και προσπαθείτε να τον μετατρέψετε σε κάποιον δεδομένο αριθμό-στόχο ~n~ εφαρμόζοντας επανειλημμένα την ακόλουθη διαδικασία. Σε κάθε βήμα, αν ~c~ είναι ο τρέχων αριθμός σας, τον χωρίζετε σε δύο θετικούς παράγοντες ~a~, ~b~ της επιλογής σας, έτσι ώστε ~c = a * b~. Στη συνέχεια προσθέτετε το ~a~ στον τρέχοντα αριθμό ~c~ για να λάβετε τον νέο τρέχοντα αριθμό σας. Αυτό σας κοστίζει ~b~ πόντους. Συνεχίζετε να το κάνετε αυτό μέχρι ο τρέχων αριθμός σας να είναι ~n~, και προσπαθείτε να το επιτύχετε αυτό με το ελάχιστο συνολικό κόστος πόντων.

Για παράδειγμα, αυτός είναι ένας τρόπος για να φτάσετε στο ~15~:

• ξεκινάτε με ~1~
• αλλάζετε το ~1~ σε ~1+1 = 2~ - το κόστος μέχρι στιγμής είναι ~1~
• αλλάζετε το ~2~ σε ~2+1 = 3~ - το κόστος μέχρι στιγμής είναι ~1+2~
• αλλάζετε το ~3~ σε ~3+3 = 6~ - το κόστος μέχρι στιγμής είναι ~1+2+1~
• αλλάζετε το ~6~ σε ~6+6 = 12~ - το κόστος μέχρι στιγμής είναι ~1+2+1+1~
• αλλάζετε το ~12~ σε ~12+3 = 15~ - έτοιμο, και το συνολικό κόστος είναι ~1+2+1+1+4=9~.

Στην πραγματικότητα, αυτό είναι το ελάχιστο δυνατό συνολικό κόστος για να φτάσουμε στο ~15~. Θέλετε να υπολογίσετε το ελάχιστο συνολικό κόστος και για άλλους τελικούς αριθμούς-στόχους.

Είσοδος

Η είσοδος θα αποτελείται από έναν ακέραιο αριθμό ~N \ge 1~. Για τουλάχιστον τα μισά αρχεία ελέγχου, ~N \le 50000~, για τουλάχιστον άλλο ένα τέταρτο των αρχείων ελέγχου ~N \le 500\;000~ και στα υπόλοιπα αρχεία ελέγχου ~N \le 5\;000\;000~.

Έξοδος

Υπολογίστε το ελάχιστο κόστος που θα σας οδηγήσει στον ~N~.

Παράδειγμα

input

15

output

9

input

2013

output

91

Επεξήγηση του δεύτερου παραδείγματος:

Για παράδειγμα, ξεκινήστε με το ~1~ και στη συνέχεια φτάστε στο ~2~, ~4~, ~5~, ~10~, ~15~, ~30~, ~60~, ~61~, ~122~, ~244~, ~305~, ~610~, ~671~, ~1342~ και και στη συνέχεια στο ~2013~.