John ให้ความสำคัญกับความปลอดภัยเป็นอย่างมาก ดังนั้นรหัสผ่านของเขาจึงยาวมาก โดยมี $n$ ตัวอักษร อย่างไรก็ตาม เขาไม่ค่อยมีความคิดสร้างสรรค์ ตัวอักษรทั้งหมดในรหัสผ่านจึงเหมือนกันทั้งหมด นั่นคือตัวอักษร a John เป็นคนใจร้อนมาก เขาจึงอยากพิมพ์รหัสผ่านให้เร็วที่สุดเท่าที่จะเป็นไปได้
เขาต้องการสร้างสตริงที่ประกอบด้วยตัวอักษร a จำนวน $n$ ตัวพอดี เขาสามารถใช้ลำดับของการกระทำต่อไปนี้: "a" (พิมพ์ตัวอักษร a), "Ctrl-A" (เลือกทั้งหมด), "Ctrl-C" (คัดลอกไปยังคลิปบอร์ด), "Ctrl-V" (วางจากคลิปบอร์ด) จงหาจำนวนการกระทำที่น้อยที่สุดที่ต้องใช้เพื่อให้ได้ผลลัพธ์ที่ต้องการ เมื่อเริ่มต้นจากช่องรหัสผ่านที่ว่างเปล่าและคลิปบอร์ดที่ว่างเปล่า
ด้านล่างนี้คือคำจำกัดความที่ชัดเจนของการกระทำทั้งสี่อย่างที่ John สามารถทำได้ในช่องรหัสผ่าน:
- การกด "a": หากไม่มีข้อความใดถูกเลือก ให้แทรกตัวอักษร
aที่ตำแหน่งของเคอร์เซอร์ (ทางด้านซ้าย) มิฉะนั้น ให้แทนที่ข้อความที่ถูกเลือกด้วยตัวอักษรaหลังจากนั้น จะไม่มีข้อความใดถูกเลือก และเคอร์เซอร์จะอยู่ที่ท้ายช่องรหัสผ่าน - การกด "Ctrl-A": เลือกข้อความทั้งหมดในช่องรหัสผ่าน
- การกด "Ctrl-C": หากไม่มีข้อความใดถูกเลือก จะไม่ทำอะไรเลย มิฉะนั้น ให้คัดลอกข้อความที่ถูกเลือกไปยังคลิปบอร์ด
- การกด "Ctrl-V": หากคลิปบอร์ดว่างเปล่า จะไม่ทำอะไรเลย มิฉะนั้น หากไม่มีข้อความใดถูกเลือก ให้แทรกข้อความจากคลิปบอร์ดที่ตำแหน่งของเคอร์เซอร์ (ทางด้านซ้าย) มิฉะนั้น ให้แทนที่ข้อความที่ถูกเลือกด้วยข้อความจากคลิปบอร์ด ในตอนท้าย จะไม่มีข้อความใดถูกเลือก และเคอร์เซอร์จะอยู่ที่ท้ายช่องรหัสผ่าน เนื้อหาในคลิปบอร์ดจะไม่เปลี่ยนแปลง
ข้อมูลนำเข้า
บรรทัดแรกและบรรทัดเดียวของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวนคือ $n$ ($1 \le n \le 10^{12}$) แทนความยาวของรหัสผ่านที่ต้องการ
ข้อมูลส่งออก
แสดงผลจำนวนเต็มหนึ่งจำนวน คือจำนวนการกระทำที่น้อยที่สุดที่ต้องใช้ในการพิมพ์รหัสผ่านตามความยาวที่ต้องการ
ตัวอย่าง
ข้อมูลนำเข้า
11
ข้อมูลส่งออก
10
หมายเหตุ
John สามารถใช้ลำดับการกระทำต่อไปนี้: a, a, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-V, Ctrl-V, Ctrl-V, a