მთელ რიცხვზე შეგიძლიათ შეასრულოთ შემდეგი სამი ტიპის ოპერაციები:

 1.     თუ რიცხვი იყოფა 3-ზე, მაშინ გაყავით 3-ზე.

2.     თუ რიცხვი იყოფა 2-ზე, გაყავით 2-ზე.

3.     გამოაკელით ერთი.

 მოცემული n ნატურალური რიცხვისთვის მოვძებნოთ ზემოთხსენებულ ოპერაციათა უმცირესი რაოდენობა, რომელთა შესრულების შემდეგაც მივიღებთ ერთს.

 შემავალი მონაცემები:  ერთი მთელი რიცხვი n (1 ≤ n ≤ 10⁶).

 გამომავალი მონაცემები: ოპერაციების ყველაზე ნაკლები რაოდენობა, რის შემდეგაც მიიღება 1.

მაგალითები

შესატანი მონაცემები
10
                  დაკოპირება

გამოსატანი მონაცემები
3
                  დაკოპირება