#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }ll x,k,m; map<ll,vector<ll> >T; map<pair<ll,pair<ll,ll> >,pair<ll,ll> >MP; set<ll>P,vis; pair<ll,ll> sol(ll x,ll k,ll m){ if(MP.count(m_p(x,m_p(k,m))))return MP[m_p(x,m_p(k,m))]; if(x==1)return m_p(1,1); if(!k)return m_p(x,1); if(P.count(x))return m_p(min(m,k)+((k+1<=m)?x:0),min(k+1,m)); pair<ll,ll>ret(0,0); for(auto y:T[x]){ if(!m)break; auto it=sol(y,k-1,m); ret.p1+=it.p1,ret.p2+=it.p2; m-=it.p2; }return MP[m_p(x,m_p(k,m))]=ret; } void slv(){ x=read(),k=read(),m=read(); if(k>m){cout<<m;return;} vector<ll>S; for(int i=1;i*1ll*i<=x;++i)if(!(x%i)){S.p_b(i);if(i*1ll*i!=x)S.p_b(x/i);} sort(S.begin(),S.end()); for(ll x:S){ if(x!=1&&(!vis.count(x)))P.insert(x); for(ll y:S){if(x%y==0)T[x].p_b(y);if(x!=1&&y%x==0)vis.insert(y);} }cout<<sol(x,k,m).p1; }int main(){ slv(); fclose(stdin); fclose(stdout); return 0; } //[1,t]->[1,1,t]