火大，为啥20

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define up(l,r,i) for(int i=(l);i<=(r);++i)
#define pb push_back

ll m,ans;
unsigned ll fib[107];
vector<unsigned ll> factor;

map<unsigned ll,int> QwQ;

int main(){
	cin>>m;
	if(m==1)cout<<1,exit(0);
	fib[0]=fib[1]=1;
	up(2,100,i)fib[i]=fib[i-1]+fib[i-2];
	up(1,100,i)QwQ[fib[i]]=i;
	for(int i=100;i>1;--i){
		if(m%fib[i]==0){
			while(m%fib[i]==0)factor.pb(fib[i]),m/=fib[i];
		}
	}
	if(m>1)cout<<"NIE",exit(0);
	for(auto x:factor){
		ans+=QwQ[x];
	}
	ans+=factor.size()-1;
	cout<<ans;
}