אירוהה וקאגויה נשבו לאחרונה בקסמו של משחק מתמטי המבוסס על מספרים שלמים.

בתחילה, הן חולקות מספר שלם חיובי $n$. שתי השחקניות מבצעות פעולות זו אחר זו; סיבוב בודד מוגדר כהשלמת פעולה אחת על ידי אירוהה ופעולה אחת על ידי קאגויה. בכל סיבוב:

1. אירוהה משחקת ראשונה: עליה לבחור מספר שלם אי-שלילי $x$ ($0\le x<n$) ולהחליף את ה-$n$ הנוכחי ב-$n+x$.

2. קאגויה משחקת שנייה: עליה לבחור מספר ראשוני $p$ המחלק את ה-$n$ הנוכחי (כלומר, $p\mid n$) ולהחליף את ה-$n$ הנוכחי ב-$\frac{n}{p}$.

הפעולות לעיל חוזרות על עצמן ברציפות. אם $n=1$ לאחר סיום של סיבוב כלשהו, המשחק מסתיים מיד.

במהלך המשחק, אירוהה שואפת למקסם את המספר הכולל של הסיבובים שישוחקו, בעוד שקאגויה שואפת למזער את המספר הכולל של הסיבובים. בהנחה ששתי השחקניות רציונליות לחלוטין ומאמצות אסטרטגיות אופטימליות, אנא קבעו את המספר הכולל של הסיבובים שהמשחק יימשך בסופו של דבר.

קלט

השורה הראשונה מכילה מספר שלם $n$ ($1\le n\le10^{18}$), המייצג את המספר ההתחלתי של המשחק.

פלט

הדפיסו שורה אחת המכילה מספר שלם, המייצג את המספר הכולל של הסיבובים שהמשחק יימשך בהינתן ששתי השחקניות משחקות באופן אופטימלי.

דוגמאות

קלט 1

1

פלט 1

0

קלט 2

9

פלט 2

4

קלט 3

16

פלט 3

5