#include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=110,N=70,lg=19,inf=1000000000000000000; int n,m,a,p10[MAXN],f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN],tf[MAXN][MAXN],tg[MAXN][MAXN],num[MAXN],Mx[MAXN]; int gtm(int x){ int res=0; while(x)res=max(res,x%10),x/=10; return res; } void slv(){ a=read(),m=read(),n=read()-1; int tmp=m; for(int i=1;i<=lg;i++)num[i]=tmp%10,tmp/=10; p10[0]=1;for(int i=1;i<=lg;i++)p10[i]=p10[i-1]*10; for(int i=0;i<=9;i++) for(int j=0;j<=9;j++)if(!i&&!j)g[1][i][j]=inf;else{ f[1][i][j]=j,g[1][i][j]=0; while(f[1][i][j]<=9){ f[1][i][j]+=max(i,f[1][i][j]); g[1][i][j]++; } f[1][i][j]-=10; } for(int o=2;o<=lg;o++) for(int i=0;i<=9;i++) for(int j=0;j<=9;j++)if(!i&&!j)g[1][i][j]=inf;else{ int F=j,G=0,t; for(int p=0;p<9;p++){ G=min(G+g[o-1][max(i,p)][F],inf); F=f[o-1][max(i,p)][F]; } f[o][i][j]=F,g[o][i][j]=G; } for(int s=0;s<10;s++){ if(!s){tf[0][s]=0,tg[0][s]=1;continue;} int F=s,G=0,mx=0,tmp=0; for(int i=lg;i>=2;i--){ for(int j=0;j<=num[i]-1;j++){ G=min(G+g[i-1][max(mx,j)][F],inf); F=f[i-1][max(mx,j)][F]; } tmp=tmp*10+num[i]; mx=max(mx,num[i]); } F=tmp*10+F; while(F<m){ F+=gtm(F); G++; } tf[0][s]=F%m,tg[0][s]=G; } for(int i=1;i<=N;i++) for(int s=0;s<10;s++) tf[i][s]=tf[i-1][tf[i-1][s]],tg[i][s]=min(tg[i-1][s]+tg[i-1][tf[i-1][s]],inf); while(n>=100){ if(a<=9&&tg[0][a]<=n){ int k=0; while(k<=63&&tg[k+1][a]<=n)k++; n-=tg[k][a]; a=tf[k][a]; continue; } if(m-a<=100){ a=(a+gtm(a))%m; n--; continue; } int tmp=a; for(int i=1;i<=lg;i++)num[i]=tmp%10,tmp/=10; for(int i=lg;i>=1;i--){ if(i==lg)Mx[i]=0;else Mx[i]=Mx[i+1]; Mx[i]=max(Mx[i],num[i]); } int d=a%10,k=1; while(!num[k+1]&&(a/p10[k+1]+1)*p10[k+1]+f[k+1][Mx[k+2]][d]<m&&g[k+1][Mx[k+2]][d]<=n)k++; n-=g[k][Mx[k+1]][d]; num[1]=f[k][Mx[k+1]][d]; num[k+1]++;a=0; for(int i=lg;i>=1;i--)a=a*10+num[i]; } while(n--)a=(a+gtm(a))%m; printf("%lld",a); } signed main(){ slv(); return 0; }