Iroha และ Kaguya เพิ่งจะหลงใหลในเกมคณิตศาสตร์ที่อิงจากจำนวนเต็ม

ในตอนเริ่มต้น พวกเธอมีจำนวนเต็มบวก $n$ ร่วมกันหนึ่งจำนวน ผู้เล่นทั้งสองผลัดกันดำเนินการ โดยหนึ่งรอบนิยามว่าทั้ง Iroha และ Kaguya ทำการดำเนินการคนละหนึ่งครั้งจนครบ ในแต่ละรอบ:

1. Iroha เริ่มก่อน: เธอต้องเลือกจำนวนเต็มไม่ลบ $x$ ($0\le x<n$) และแทนค่า $n$ ปัจจุบันด้วย $n+x$

2. Kaguya เล่นทีหลัง: เธอต้องเลือกจำนวนเฉพาะ $p$ ที่หาร $n$ ปัจจุบันลงตัว (กล่าวคือ $p\mid n$) และแทนค่า $n$ ปัจจุบันด้วย $\frac{n}{p}$

การดำเนินการข้างต้นจะทำซ้ำอย่างต่อเนื่อง หาก $n=1$ หลังจากสิ้นสุดรอบใด ๆ เกมจะจบลงทันที

ในระหว่างเกม Iroha ต้องการทำให้จำนวนรอบทั้งหมดที่เล่นมีค่ามากที่สุด ในขณะที่ Kaguya ต้องการทำให้จำนวนรอบทั้งหมดมีค่าน้อยที่สุด สมมติว่าผู้เล่นทั้งสองมีเหตุผลอย่างสมบูรณ์และใช้กลยุทธ์ที่เหมาะสมที่สุด จงหาว่าท้ายที่สุดแล้วเกมนี้จะดำเนินไปทั้งหมดกี่รอบ

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1\le n\le10^{18}$) แทนจำนวนเริ่มต้นของเกม

ข้อมูลส่งออก

แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน แทนจำนวนรอบทั้งหมดที่เกมจะดำเนินไปเมื่อผู้เล่นทั้งสองฝ่ายเล่นอย่างเหมาะสมที่สุด

ตัวอย่าง

ข้อมูลนำเข้า 1

1

ข้อมูลส่งออก 1

0

ข้อมูลนำเข้า 2

9

ข้อมูลส่งออก 2

4

ข้อมูลนำเข้า 3

16

ข้อมูลส่งออก 3

5