След като изследването на простите числа при деление на две не доведе до нищо хубаво, Ели реши да смени стратегията си. Сега тя ще дели на числа на Фибоначи.

Числата на Фибоначи са редица от естествени числа, която се дефинира рекурсивно по следния начин: F₀ = 0, F₁ = 1, F_i = F_i-1 + F_i-2, за i > 1. Първите няколко числа на Фибоначи са 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Ели си избира едно начално естествено число N₀ и прилага следните операции. В началото тя казва, че не е намерила нито едно просто число. Ако числото N₀ е просто тя отбелязва, че е намерила едно просто число. След това тя си избира някое число на Фибоначи и дели N₀ целочислено на него. Тъй като делението на 0 не е дефинирано, а на 1 няма голям смисъл, ще разглеждаме само деления на числа на Фибоначи, които са по-големи или равни на 2.

Например ако N₀ е било 47 тя може да избере третото число на Фибоначи, което е 2, и да го раздели на него, получавайки числото N₁ = 47 / 2 = 23. Двадесет и три също е просто, затова Ели си отбелязва, че е намерила две прости числа. След това тя отново избира число на Фибоначи – например отново 2 и получава N₂ = 23 / 2 = 11. То също е просто, затова Ели си отбелязва, че е намерила 3 прости числа. По-нататък тя може да избере друго число на Фибоначи – например 3 – и да получи N₃ = 11 / 3 = 3. То отново е просто, затова тя си отбелязва, че е намерила четвърто просто число. Оттук нататък което и число на Фибоначи да избере тя ще получи 0 или 1, никое от които не е просто и от което не могат да се получат други прости, следователно Ели приключва работата си.

Забележете обаче, че изборът на кое число на Фибоначи да дели Ели е доста важен. Например тя можеше да избере да раздели първо на 3, после на 2 и на 2, получавайки редицата {47, 15, 7, 3}, където тя би намерила 3 прости числа. Всъщност, при 47 оптималната стратегия за Ели би била да дели само и единствено на 2, получавайки {47, 23, 11, 5, 2} – общо 5 прости числа. Това, обаче, не винаги е вярно. При числото 65 би било най-изгодно за нея да дели на 5, и после отново на 5 (или пък на 5, после на 2 и отново на 2) получавайки съответно редиците {65, 13, 2} или {65, 13, 6, 3}, всяка от които съдържа по 2 прости числа.

По дадено начално число N₀ да определите колко най-много прости числа може да намери Ели ако ползва оптимални деления. На единствен ред на стандартния вход ще бъде зададено цялото числото N₀, с което започва Ели. На стандартния изход изведете едно единствено цяло число – колко най-много прости числа може да намери Ели, спазвайки описания алгоритъм.

• 1 ≤ N₀ ≤ 10¹²

Примерен Вход	Примерен Изход
47	5
65	2
42133742	10