#include<boost/iterator/transform_iterator.hpp>
#include<bits/stdc++.h>
#define M make_pair
#define I boost::make_transform_iterator
#define Y begin
#define V end
#define S(x)Y(x),V(x),
#define K(x,y)lower_bound(S(x)y)
#define W vector
#define X set_union
#define F first
#define E second
#define A return
#define O ;auto
#define L ::iterator i,decltype(i)j,T m){if
#define B resize
#define C size()
#define D rbegin(v)
#define H [](Q a,Q b){A
#define J ;using
#define Z ,Y(v),prev(V(v)),m)
J N=int J namespace std J P=pair<N,N>J Q=pair<N,P>J T=int64_t O o=H a.F<b.F;};string t;T G=10;P R(N p,P s,list<W<N>>L(i==j)A s;s=R(p*G%m,s,next(i),j,m);T k=s.E*G,r=s.F,d=k/m;r=!binary_search(S(*i)r)?k++,(r+m-p)%m:r;if(d|t.C)t+='0'+d;A{r,k%m};}void U(N x,N y,W<Q>L(y+~x){T z=x+y>>1 O k=lower_bound(i,j,M(N((m*z+9)/G),M(0,0)));U(x,z,i,k,m);U(z,y,k,j,m);inplace_merge(i,k,j,H M(a.F,a.E.E)<M(b.F,b.E.E);});}else{O k=i;for(;k-j;k++)k->F=k->F*G%m;}}Q $(N a){A{a,{a,0}};}string g(N m){if(m==1)A"1";list<W<N>>v{{0}};W<Q>a,_;for(N s=1,p=1,q;;){T r=p;v.emplace_back(D->C*2);W<N>&c=*D,&e=*next(D)O f=[m,r](N a){A(a+r)%m;}O n=K(e,p)O l=I(K(e,m-p),f);c.B(X(n,V(e),I(Y(e),f),l,X(Y(e),n,l,I(V(e),f),Y(c)))-Y(c))O w=K(a,M(q=m-r*p%m,M(0,0)))O y=[m,r,q,s](Q a){O[x,y]=a;A M((x+(T)q)%m,M((y.F+r)%m,s+y.E));}O z=I(K(a,M(m-q,M(0,0))),y);_.B(a.C*2+1)O i=X(Y(a),w,z,I(V(a),y),Y(_),o);if(w==V(a)||w->F-q)*i++={q,{p,s}};_.B(X(w,V(a),I(Y(a),y),z,i,o)-Y(_));a.swap(_);s+=e.C;p=p*G%m;U(0,G,S(a)m);a.B(unique(S(a)H a.F==b.F;})-Y(a));W<Q>h;set_intersection(S(a)I(Y(c),$),I(V(c),$),back_inserter(h),o);if(h.C){Q b=*min_element(S(h)H a.E.E<b.E.E;});t="";R(1,{b.F,R(1,{b.E.F,0}Z.E}Z;A t;}}}
 
N main(N c,char**v){if(c>1)for(fstream o(v[c=1]);c<=1e4;)o<<g(c++)<<'\n';else cin>>c,cout<<g(c)<<'\n';}

I2luY2x1ZGU8Ym9vc3QvaXRlcmF0b3IvdHJhbnNmb3JtX2l0ZXJhdG9yLmhwcD4KI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBNIG1ha2VfcGFpcgojZGVmaW5lIEkgYm9vc3Q6Om1ha2VfdHJhbnNmb3JtX2l0ZXJhdG9yCiNkZWZpbmUgWSBiZWdpbgojZGVmaW5lIFYgZW5kCiNkZWZpbmUgUyh4KVkoeCksVih4KSwKI2RlZmluZSBLKHgseSlsb3dlcl9ib3VuZChTKHgpeSkKI2RlZmluZSBXIHZlY3RvcgojZGVmaW5lIFggc2V0X3VuaW9uCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIEUgc2Vjb25kCiNkZWZpbmUgQSByZXR1cm4KI2RlZmluZSBPIDthdXRvCiNkZWZpbmUgTCA6Oml0ZXJhdG9yIGksZGVjbHR5cGUoaSlqLFQgbSl7aWYKI2RlZmluZSBCIHJlc2l6ZQojZGVmaW5lIEMgc2l6ZSgpCiNkZWZpbmUgRCByYmVnaW4odikKI2RlZmluZSBIIFtdKFEgYSxRIGIpe0EKI2RlZmluZSBKIDt1c2luZwojZGVmaW5lIFogLFkodikscHJldihWKHYpKSxtKQpKIE49aW50IEogbmFtZXNwYWNlIHN0ZCBKIFA9cGFpcjxOLE4+SiBRPXBhaXI8TixQPkogVD1pbnQ2NF90IE8gbz1IIGEuRjxiLkY7fTtzdHJpbmcgdDtUIEc9MTA7UCBSKE4gcCxQIHMsbGlzdDxXPE4+PkwoaT09ailBIHM7cz1SKHAqRyVtLHMsbmV4dChpKSxqLG0pO1Qgaz1zLkUqRyxyPXMuRixkPWsvbTtyPSFiaW5hcnlfc2VhcmNoKFMoKmkpcik/aysrLChyK20tcCklbTpyO2lmKGR8dC5DKXQrPScwJytkO0F7cixrJW19O312b2lkIFUoTiB4LE4geSxXPFE+TCh5K354KXtUIHo9eCt5Pj4xIE8gaz1sb3dlcl9ib3VuZChpLGosTShOKChtKnorOSkvRyksTSgwLDApKSk7VSh4LHosaSxrLG0pO1Uoeix5LGssaixtKTtpbnBsYWNlX21lcmdlKGksayxqLEggTShhLkYsYS5FLkUpPE0oYi5GLGIuRS5FKTt9KTt9ZWxzZXtPIGs9aTtmb3IoO2stajtrKyspay0+Rj1rLT5GKkclbTt9fVEgJChOIGEpe0F7YSx7YSwwfX07fXN0cmluZyBnKE4gbSl7aWYobT09MSlBIjEiO2xpc3Q8VzxOPj52e3swfX07VzxRPmEsXztmb3IoTiBzPTEscD0xLHE7Oyl7VCByPXA7di5lbXBsYWNlX2JhY2soRC0+QyoyKTtXPE4+JmM9KkQsJmU9Km5leHQoRClPIGY9W20scl0oTiBhKXtBKGErciklbTt9TyBuPUsoZSxwKU8gbD1JKEsoZSxtLXApLGYpO2MuQihYKG4sVihlKSxJKFkoZSksZiksbCxYKFkoZSksbixsLEkoVihlKSxmKSxZKGMpKSktWShjKSlPIHc9SyhhLE0ocT1tLXIqcCVtLE0oMCwwKSkpTyB5PVttLHIscSxzXShRIGEpe09beCx5XT1hO0EgTSgoeCsoVClxKSVtLE0oKHkuRityKSVtLHMreS5FKSk7fU8gej1JKEsoYSxNKG0tcSxNKDAsMCkpKSx5KTtfLkIoYS5DKjIrMSlPIGk9WChZKGEpLHcseixJKFYoYSkseSksWShfKSxvKTtpZih3PT1WKGEpfHx3LT5GLXEpKmkrKz17cSx7cCxzfX07Xy5CKFgodyxWKGEpLEkoWShhKSx5KSx6LGksbyktWShfKSk7YS5zd2FwKF8pO3MrPWUuQztwPXAqRyVtO1UoMCxHLFMoYSltKTthLkIodW5pcXVlKFMoYSlIIGEuRj09Yi5GO30pLVkoYSkpO1c8UT5oO3NldF9pbnRlcnNlY3Rpb24oUyhhKUkoWShjKSwkKSxJKFYoYyksJCksYmFja19pbnNlcnRlcihoKSxvKTtpZihoLkMpe1EgYj0qbWluX2VsZW1lbnQoUyhoKUggYS5FLkU8Yi5FLkU7fSk7dD0iIjtSKDEse2IuRixSKDEse2IuRS5GLDB9Wi5FfVo7QSB0O319fQoKTiBtYWluKE4gYyxjaGFyKip2KXtpZihjPjEpZm9yKGZzdHJlYW0gbyh2W2M9MV0pO2M8PTFlNDspbzw8ZyhjKyspPDwnXG4nO2Vsc2UgY2luPj5jLGNvdXQ8PGcoYyk8PCdcbic7fQ==

MTk5OTk5OTk5OA==

1999999998