Masala F
Raqamli pechenyelar
Azizbek sehrli raqam-pechenyelarni bir-biriga ulab, ulardan bir katta butun son yasadi. Endi u ushbu son ustida quyidagicha o‘yin o‘ynaydi:
- Har qadamda aniq bitta raqamni (istalgan joydan) o‘chirib tashlaydi.
- O‘chirilgan raqamdan so‘ng qolgan raqamlar bir-biriga yopishib, tartibi saqlanadi.
- Agar raqamlarning boshida nol(lar) paydo bo‘lsa, ularni birdan olib tashlaydi (ya’ni, oldinda nol raqami qolmaydi).
- Har safar yangi hosil bo‘lgan son tub son bo‘lsa, o‘yin davom etadi. Agar tub bo‘lmasa, o‘yin shu zahoti to‘xtaydi.
Boshlang‘ich son ham hisobga olinadi: agar tub bo‘lsa, o‘zi ham birinchi holat sifatida qabul qilinadi.
Shunday tartibda raqamlarni o‘chirish ketma-ketligini eng zo‘r tanlab, Azizbek eng ko‘p necha marta tub son bilan uchrashishi mumkinligini (boshlang‘ich holat ham qo‘shiladi) aniqlang.
Sizning vazifangiz: Berilgan son \(N\) uchun yuqoridagi o‘yinda raqamlarni qanday ketma-ketlikda o‘chirish mumkinligi ichida, ketma-ket tub sonlar maksimal sonini chiqaring.
Kiruvchi ma'lumotlar:
Yagona qatorda natural son - \(N\) beriladi
\(1 \le N \le 10^9\)
Chiquvchi ma'lumotlar:
Bitta butun son chiqaring — jarayon davomida ketma-ket tub sonlar maksimal sonini.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
11 |
1 |
| 2 |
2 |
1 |
| 3 |
773 |
3 |
| 4 |
300007 |
2 |
| 5 |
15 |
0 |
Telegram kanalimizga obuna bo'ling