أصبحت إيروها وكاغويا مؤخرًا مفتونتين بلعبة رياضية تعتمد على الأعداد الصحيحة.

في البداية، تتشاركان عددًا صحيحًا موجبًا $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