Yenə də zəncir

N halqadan ibarət zəncirə baxaq. Zəncirdən elə minimal sayda halqa ayırmaq lazımdır ki, qalan hissələrdən 1-dən N-ə qədər halqa ehtiva edən istənilən uzunluqda zəncir yığmaq mümkün olsun. Yeni zəncirləri qurarkən ayrılmış halqalardan da istifadə etmək olar.

Məsələn, N = 21 olarsa, yalnız 2 halqanı elə ayırmaq olar ki, 3, 5 и 11 uzunluğunda parçalar alınsın. İki ayrılmış halqa vahid uzunluqlu parça sayılır.

Cari zəncirin verilmiş N uzunluğuna görə təsvir olunmuş məqsədə çatmaq üçün zəncirdən ayırılacaq halqaların minimal sayını tapın.

Giriş verilənləri

Yeganə N (1 ≤ N ≤ 10^9) tam ədədi.

Çıxış verilənləri

Ayırılacaq halqaların minimal sayı.

Nümunələr