#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
#pragma optimize("fast-math")

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
#define endl '\n'
#define ull unsigned long long
#define si short int
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define piii pair<pair<int, int>, int>
#define all(vec) (vec).begin(), (vec).end()
#define piiii pair<pair<int, int>, pair<int, int>>
#define fr(a, from, c) for(int a=(from); (a)<(c); (a)++)

/*-----------------------------------------------------SegTree---------------------------------------------*/

/*
int mxn11 = (int) (3e5 + 2);
vector<int> t(4 * mxn11 + 1, 0);
vector<int> tAdd(4 * mxn11 + 1, 0);

void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = vl;
    } else {
        int tmp = (vl + vr) >> 1;
        build((v << 1), vl, tmp);
        build((v << 1) + 1, tmp + 1, vr);
        t[v] = 0;
    }
}

void push(int v){
    tAdd[2*v]+=tAdd[v];
    tAdd[2*v+1]+=tAdd[v];
    t[v]+=tAdd[v];
    tAdd[v]=0;
}
int get(int v, int vl, int vr, int l, int r) {
    if (l > r) return 0;
    if (vl == l && vr == r) {
        return t[v]+tAdd[v];
    }
    int tmp = (vl + vr) >> 1;
    push(v);
    int a = get(v << 1, vl, tmp, l, mun(tmp, r));
    int b = get((v << 1) + 1, tmp + 1, vr, mux(tmp + 1, l), r);
    return a+b;
}

void update(int v, int vl, int vr, int l, int r, int x){
    if(l>r) return;
    if(vl==l && vr==r){
        tAdd[v]+=x;
        return;
    }
    int tmp=(vl+vr)/2;
    push(v);
    update(2*v, vl, tmp, l, min(r, tmp), x);
    update(2*v+1, tmp+1, vr, max(l, tmp+1), r, x);
    t[v] = t[2 * v] + tAdd[2 * v] + t[2 * v + 1] + tAdd[2 * v + 1];
}
*/


/*-----------------------------------------------------SegTree---------------------------------------------*/
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/*-----------------------------------------------------OperatorsOverloaded---------------------------------*/
template<typename T, typename U>
ostream &operator<<(ostream &o, pair<T, U> p) {
    o << p.first << " " << p.second << endl;
    return o;
}

template<typename T>
istream &operator>>(istream &o, vector<T> &arr) {
    for (int i = 0; i < arr.size(); i++) o >> arr[i];
    return o;
}

template<typename T>
ostream &operator<<(ostream &o, vector<T> &arr) {
    for (int i = 0; i < arr.size(); i++) o << arr[i] << " ";
    o << endl;
    return o;
}
/*-----------------------------------------------------OperatorsOverloaded---------------------------------*/
/*#ifdef ALLOC_LOCAL
const int ML_ = 450;
char mem_[ML_ * 1024 * 1024];
size_t _ptr = 0, _magic = 21323400;
void * operator new(size_t cnt) { if (_ptr + cnt < sizeof mem_) { _ptr += cnt; return  mem_ + _ptr - cnt; } else { assert(false);  _ptr = cnt + _magic; return mem_ + _magic; } }
void operator delete(void *) {}
#endif //ALLOC_LOCAL*/
int mux(int a, int b) {
    if (a > b) return a;
    return b;
}

int mun(int a, int b) {
    if (a < b) return a;
    return b;
}
/*-----------------------------------------------------MATH------------------------------------------------*/
inline ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


inline ll gcdex(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll xx, yy;
    ll gc = gcdex(b, a % b, yy, xx);
    x = xx;
    y = yy - (a / b) * xx;
    return gc;
}

inline ll pwm(ll xx, ll pow, ll MD) {
    if (pow < 0) { pow = pow % (MD - 1) + MD - 1; }
    ll mlt = 1;
    while (pow) {
        if (pow & 1) {
            mlt *= xx;
            mlt %= MD;
        }
        xx *= xx;
        pow >>= 1;
        xx %= MD;
    }
    return mlt;
}

inline int inv(ll r, int _mod) { return pwm(r % _mod, _mod - 2, _mod); }

inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
    if (pow == 0) {
        return 0;
    }
    int hpow = 1 << (pow - 1);
    int seg = (x < hpow) ? (
            (y < hpow) ? 0 : 3
    ) : (
                      (y < hpow) ? 1 : 2
              );
    seg = (seg + rotate) & 3;
    const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
    int64_t ans = seg * subSquareSize;
    int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

/*-----------------------------------------------------MATH------------------------------------------------*/
const int mod=1e9+7;
//vector<ll> arr(500, 0);
vector<ll> arr(1000, 0);
//vector<ll> arr;
bool lol(ll kek){
    ll last=kek%10;
    while(kek>0){
        if(abs(kek%10 - last)>=2) return false;
        last=kek%10;
        kek/=10;
    }
    return true;
}

void precalc(){
    arr[0]=1;
    arr[1]=887;
    arr[2]=4454;
    arr[3]=8789;
    arr[4]=21123;
    arr[5]=33323;
    arr[6]=45443;
    arr[7]=56777;
    arr[8]=76676;
    arr[9]=88889;
    arr[10]=110112;
    arr[11]=123210;
    arr[12]=221123;
    arr[13]=233323;
    arr[14]=323321;
    arr[15]=343212;
    arr[16]=432333;
    arr[17]=444445;
    arr[18]=456565;
    arr[19]=545677;
    arr[20]=565567;
    arr[21]=655544;
    arr[22]=667656;
    arr[23]=765433;
    arr[24]=776776;
    arr[25]=788998;
    arr[26]=887766;
    arr[27]=987778;
    arr[28]=1001100;
    arr[29]=1101112;
    arr[30]=1122112;
    arr[31]=1212234;
    arr[32]=1232233;
    arr[33]=2110000;
    arr[34]=2122321;
    arr[35]=2221011;
    arr[36]=2233212;
    arr[37]=2323210;
    arr[38]=2334545;
    arr[39]=3210123;
    arr[40]=3223221;
    arr[41]=3234556;
    arr[42]=3332333;
    arr[43]=3344445;
    arr[44]=3434344;
    arr[45]=3445678;
    arr[46]=4321223;
    arr[47]=4333345;
    arr[48]=4345543;
    arr[49]=4443212;
    arr[50]=4454554;
    arr[51]=4544444;
    arr[52]=4556556;
    arr[53]=4567898;
    arr[54]=5443432;
    arr[55]=5455544;
    arr[56]=5545434;
    arr[57]=5556776;
    arr[58]=5654445;
    arr[59]=5666565;
    arr[60]=5678765;
    arr[61]=6545676;
    arr[62]=6565566;
    arr[63]=6655543;
    arr[64]=6667655;
    arr[65]=6765432;
    arr[66]=6776767;
    arr[67]=6788989;
    arr[68]=7665443;
    arr[69]=7676778;
    arr[70]=7766776;
    arr[71]=7778898;
    arr[72]=7877667;
    arr[73]=7889988;
    arr[74]=8767677;
    arr[75]=8787676;
    arr[76]=8877876;
    arr[77]=8898876;
    arr[78]=8998888;
    arr[79]=9887665;
    arr[80]=9987677;
    arr[81]=10000122;
    arr[82]=10101010;
    arr[83]=10121232;
    arr[84]=11010112;
    arr[85]=11111000;
    arr[86]=11123222;
    arr[87]=11221221;
    arr[88]=11233343;
    arr[89]=12111210;
    arr[90]=12123345;
    arr[91]=12222123;
    arr[92]=12234322;
    arr[93]=12323456;
    arr[94]=12343433;
    arr[95]=21010011;
    arr[96]=21110110;
    arr[97]=21122344;
    arr[98]=21221121;
    arr[99]=21233321;
    arr[100]=22111110;
    arr[101]=22123323;
    arr[102]=22222101;
    arr[103]=22233444;
    arr[104]=22323434;
    arr[105]=22343333;
    arr[106]=23211232;
    arr[107]=23223445;
    arr[108]=23321221;
    arr[109]=23333343;
    arr[110]=23345455;
    arr[111]=23443210;
    arr[112]=23454544;
    arr[113]=32110011;
    arr[114]=32122332;
    arr[115]=32221101;
    arr[116]=32233223;
    arr[117]=32323221;
    arr[118]=32334556;
    arr[119]=33211010;
    arr[120]=33223232;
    arr[121]=33234567;
    arr[122]=33332344;
    arr[123]=33344456;
    arr[124]=33434433;
    arr[125]=33454323;
    arr[126]=34321234;
    arr[127]=34333434;
    arr[128]=34345554;
    arr[129]=34443223;
    arr[130]=34454565;
    arr[131]=34544455;
    arr[132]=34556567;
    arr[133]=43210001;
    arr[134]=43222322;
    arr[135]=43234443;
    arr[136]=43332212;
    arr[137]=43344332;
    arr[138]=43433445;
    arr[139]=43445565;
    arr[140]=44321110;
    arr[141]=44333232;
    arr[142]=44344566;
    arr[143]=44434543;
    arr[144]=44454433;
    arr[145]=44544323;
    arr[146]=44555665;
    arr[147]=44567777;
    arr[148]=45443233;
    arr[149]=45454567;
    arr[150]=45544543;
    arr[151]=45556655;
    arr[152]=45654332;
    arr[153]=45665666;
    arr[154]=45677787;
    arr[155]=54323433;
    arr[156]=54343332;
    arr[157]=54433223;
    arr[158]=54444565;
    arr[159]=54456677;
    arr[160]=54554345;
    arr[161]=54566543;
    arr[162]=55433443;
    arr[163]=55445555;
    arr[164]=55543223;
    arr[165]=55554565;
    arr[166]=55566677;
    arr[167]=55656654;
    arr[168]=55676545;
    arr[169]=56544321;
    arr[170]=56555655;
    arr[171]=56567767;
    arr[172]=56665444;
    arr[173]=56676787;
    arr[174]=56766777;
    arr[175]=56778899;
    arr[176]=65433233;
    arr[177]=65444567;
    arr[178]=65456765;
    arr[179]=65554433;
    arr[180]=65566545;
    arr[181]=65655666;
    arr[182]=65667778;
    arr[183]=66543333;
    arr[184]=66555445;
    arr[185]=66566787;
    arr[186]=66656678;
    arr[187]=66676655;
    arr[188]=66766567;
    arr[189]=66778767;
    arr[190]=67654544;
    arr[191]=67666656;
    arr[192]=67678778;
    arr[193]=67776554;
    arr[194]=67788767;
    arr[195]=67878889;
    arr[196]=67899988;
    arr[197]=76554454;
    arr[198]=76566566;
    arr[199]=76656543;
    arr[200]=76667877;
    arr[201]=76765654;
    arr[202]=76777767;
    arr[203]=77654323;
    arr[204]=77665665;
    arr[205]=77677778;
    arr[206]=77767776;
    arr[207]=77787767;
    arr[208]=77877889;
    arr[209]=77898889;
    arr[210]=78767899;
    arr[211]=78787898;
    arr[212]=78878877;
    arr[213]=78899889;
    arr[214]=78999988;
    arr[215]=87665565;
    arr[216]=87677678;
    arr[217]=87767676;
    arr[218]=87787667;
    arr[219]=87877789;
    arr[220]=87898789;
    arr[221]=88767877;
    arr[222]=88787876;
    arr[223]=88878777;
    arr[224]=88898999;
    arr[225]=88999887;
    arr[226]=89887787;
    arr[227]=89987877;
    arr[228]=98765667;
    arr[229]=98777788;
    arr[230]=98876566;
    arr[231]=98888787;
    arr[232]=98988877;
    arr[233]=99877777;
    arr[234]=99898777;
    arr[235]=99998789;
    arr[236]=100012111;
    arr[237]=100112123;
    arr[238]=101000101;
    arr[239]=101100121;
    arr[240]=101121211;
    arr[241]=101212112;
    arr[242]=101232111;
    arr[243]=110001121;
    arr[244]=110101211;
    arr[245]=110122211;
    arr[246]=111011111;
    arr[247]=111111123;
    arr[248]=111123344;
    arr[249]=111222122;
    arr[250]=111234321;
    arr[251]=112112111;
    arr[252]=112210010;
    arr[253]=112222323;
    arr[254]=112234444;
    arr[255]=112332221;
    arr[256]=112344333;
    arr[257]=121011010;
    arr[258]=121111101;
    arr[259]=121123322;
    arr[260]=121222100;
    arr[261]=121233443;
    arr[262]=122111232;
    arr[263]=122123445;
    arr[264]=122222223;
    arr[265]=122234344;
    arr[266]=122332121;
    arr[267]=122343455;
    arr[268]=123212211;
    arr[269]=123232210;
    arr[270]=123322122;
    arr[271]=123334321;
    arr[272]=123345655;
    arr[273]=123443332;
    arr[274]=123455444;
    arr[275]=210011010;
    arr[276]=210111101;
    arr[277]=210123322;
    arr[278]=211012223;
    arr[279]=211112321;
    arr[280]=211211011;
    arr[281]=211223233;
    arr[282]=212100000;
    arr[283]=212121012;
    arr[284]=212211221;
    arr[285]=212223434;
    arr[286]=212321210;
    arr[287]=212333332;
    arr[288]=212345444;
    arr[289]=221012123;
    arr[290]=221112221;
    arr[291]=221210121;
    arr[292]=221223211;
    arr[293]=221234554;
    arr[294]=222112344;
    arr[295]=222211121;
    arr[296]=222223334;
    arr[297]=222321110;
    arr[298]=222333232;
    arr[299]=222344566;
    arr[300]=223221121;
    arr[301]=223233321;
    arr[302]=223323233;
    arr[303]=223343210;
    arr[304]=223432323;
    arr[305]=223444443;
    arr[306]=223456555;
    arr[307]=232112123;
    arr[308]=232210101;
    arr[309]=232222343;
    arr[310]=232234456;
    arr[311]=232332233;
    arr[312]=232344345;
    arr[313]=233212323;
    arr[314]=233232322;
    arr[315]=233322234;
    arr[316]=233334433;
    arr[317]=233432110;
    arr[318]=233443444;
    arr[319]=233455556;
    arr[320]=234323332;
    arr[321]=234343223;
    arr[322]=234432344;
    arr[323]=234444456;
    arr[324]=234456654;
    arr[325]=234554322;
    arr[326]=234565656;
    arr[327]=321010100;
    arr[328]=321110112;
    arr[329]=321123210;
    arr[330]=321221123;
    arr[331]=321233323;
    arr[332]=322111112;
    arr[333]=322123333;
    arr[334]=322222111;
    arr[335]=322233454;
    arr[336]=322323444;
    arr[337]=322343343;
    arr[338]=323211234;
    arr[339]=323223455;
    arr[340]=323321223;
    arr[341]=323333345;
    arr[342]=323345543;
    arr[343]=323443212;
    arr[344]=323454554;
    arr[345]=332110100;
    arr[346]=332122334;
    arr[347]=332221111;
    arr[348]=332233233;
    arr[349]=332323223;
    arr[350]=332334566;
    arr[351]=333211012;
    arr[352]=333223234;
    arr[353]=333321001;
    arr[354]=333333210;
    arr[355]=333344544;
    arr[356]=333434443;
    arr[357]=333454333;
    arr[358]=334322101;
    arr[359]=334333444;
    arr[360]=334345556;
    arr[361]=334443233;
    arr[362]=334454567;
    arr[363]=334544543;
    arr[364]=334556655;
    arr[365]=343210011;
    arr[366]=343222332;
    arr[367]=343234445;
    arr[368]=343332222;
    arr[369]=343344334;
    arr[370]=343433455;
    arr[371]=343445567;
    arr[372]=344321112;
    arr[373]=344333234;
    arr[374]=344345432;
    arr[375]=344434545;
    arr[376]=344454443;
    arr[377]=344544333;
    arr[378]=344555667;
    arr[379]=344567787;
    arr[380]=345443321;
    arr[381]=345455433;
    arr[382]=345544545;
    arr[383]=345556665;
    arr[384]=345654334;
    arr[385]=345665676;
    arr[386]=345677789;
    arr[387]=432111234;
    arr[388]=432123455;
    arr[389]=432222233;
    arr[390]=432234432;
    arr[391]=432332123;
    arr[392]=432344321;
    arr[393]=433212221;
    arr[394]=433232212;
    arr[395]=433322210;
    arr[396]=433334323;
    arr[397]=433345665;
    arr[398]=433443334;
    arr[399]=433455454;
    arr[400]=434323222;
    arr[401]=434334565;
    arr[402]=434432234;
    arr[403]=434444432;
    arr[404]=434456544;
    arr[405]=434545656;
    arr[406]=434565554;
    arr[407]=443211232;
    arr[408]=443223445;
    arr[409]=443321221;
    arr[410]=443333343;
    arr[411]=443345455;
    arr[412]=443443210;
    arr[413]=443454544;
    arr[414]=444322234;
    arr[415]=444334433;
    arr[416]=444432110;
    arr[417]=444443444;
    arr[418]=444455556;
    arr[419]=444545454;
    arr[420]=444556788;
    arr[421]=445432322;
    arr[422]=445444434;
    arr[423]=445456554;
    arr[424]=445545666;
    arr[425]=445565556;
    arr[426]=445655455;
    arr[427]=445666789;
    arr[428]=445678998;
    arr[429]=454332343;
    arr[430]=454344455;
    arr[431]=454434432;
    arr[432]=454454322;
    arr[433]=454543434;
    arr[434]=454555554;
    arr[435]=454567666;
    arr[436]=455434566;
    arr[437]=455454456;
    arr[438]=455544432;
    arr[439]=455556544;
    arr[440]=455567878;
    arr[441]=455665555;
    arr[442]=455677676;
    arr[443]=456545444;
    arr[444]=456556778;
    arr[445]=456654455;
    arr[446]=456666567;
    arr[447]=456678767;
    arr[448]=456776543;
    arr[449]=456787899;
    arr[450]=543221011;
    arr[451]=543233212;
    arr[452]=543323210;
    arr[453]=543334545;
    arr[454]=543432222;
    arr[455]=543444334;
    arr[456]=543455676;
    arr[457]=544323444;
    arr[458]=544343343;
    arr[459]=544433234;
    arr[460]=544445432;
    arr[461]=544456766;
    arr[462]=544554434;
    arr[463]=544566554;
    arr[464]=545433454;
    arr[465]=545445566;
    arr[466]=545543234;
    arr[467]=545555432;
    arr[468]=545566766;
    arr[469]=545656665;
    arr[470]=545676556;
    arr[471]=554322210;
    arr[472]=554334323;
    arr[473]=554345665;
    arr[474]=554443334;
    arr[475]=554455454;
    arr[476]=554544566;
    arr[477]=554556678;
    arr[478]=555432212;
    arr[479]=555444332;
    arr[480]=555455666;
    arr[481]=555545556;
    arr[482]=555565454;
    arr[483]=555654567;
    arr[484]=555666765;
    arr[485]=555678887;
    arr[486]=556554432;
    arr[487]=556566544;
    arr[488]=556655665;
    arr[489]=556667777;
    arr[490]=556765554;
    arr[491]=556777667;
    arr[492]=556789988;
    arr[493]=565443344;
    arr[494]=565455456;
    arr[495]=565545432;
    arr[496]=565556766;
    arr[497]=565654443;
    arr[498]=565666555;
    arr[499]=565677898;
    arr[500]=566545666;
    arr[501]=566565556;
    arr[502]=566655455;
    arr[503]=566666789;
    arr[504]=566678998;
    arr[505]=566776765;
    arr[506]=566788987;
    arr[507]=567665433;
    arr[508]=567676776;
    arr[509]=567766766;
    arr[510]=567778888;
    arr[511]=567877665;
    arr[512]=567889899;
    arr[513]=654323323;
    arr[514]=654343222;
    arr[515]=654432343;
    arr[516]=654444455;
    arr[517]=654456567;
    arr[518]=654554321;
    arr[519]=654565655;
    arr[520]=655433333;
    arr[521]=655445445;
    arr[522]=655456787;
    arr[523]=655554455;
    arr[524]=655566567;
    arr[525]=655656544;
    arr[526]=655667878;
    arr[527]=656543433;
    arr[528]=656555545;
    arr[529]=656567665;
    arr[530]=656656778;
    arr[531]=656676677;
    arr[532]=656766667;
    arr[533]=656778789;
    arr[534]=665432345;
    arr[535]=665444543;
    arr[536]=665456655;
    arr[537]=665554323;
    arr[538]=665565665;
    arr[539]=665655556;
    arr[540]=665667676;
    arr[541]=666543223;
    arr[542]=666554565;
    arr[543]=666566677;
    arr[544]=666656654;
    arr[545]=666676545;
    arr[546]=666766543;
    arr[547]=666777878;
    arr[548]=667654434;
    arr[549]=667666554;
    arr[550]=667677889;
    arr[551]=667767887;
    arr[552]=667787878;
    arr[553]=667878787;
    arr[554]=667899877;
    arr[555]=676554344;
    arr[556]=676565678;
    arr[557]=676655655;
    arr[558]=676667767;
    arr[559]=676765544;
    arr[560]=676777665;
    arr[561]=676789899;
    arr[562]=677665555;
    arr[563]=677677676;
    arr[564]=677767666;
    arr[565]=677787665;
    arr[566]=677877787;
    arr[567]=677898787;
    arr[568]=678767789;
    arr[569]=678787788;
    arr[570]=678878767;
    arr[571]=678898989;
    arr[572]=678999877;
    arr[573]=765443234;
    arr[574]=765455432;
    arr[575]=765544544;
    arr[576]=765556656;
    arr[577]=765654333;
    arr[578]=765665667;
    arr[579]=765677788;
    arr[580]=766545556;
    arr[581]=766565454;
    arr[582]=766654567;
    arr[583]=766666765;
    arr[584]=766678887;
    arr[585]=766776655;
    arr[586]=766788876;
    arr[587]=767656767;
    arr[588]=767676666;
    arr[589]=767766656;
    arr[590]=767778778;
    arr[591]=767876777;
    arr[592]=767888999;
    arr[593]=776544565;
    arr[594]=776556677;
    arr[595]=776654432;
    arr[596]=776666544;
    arr[597]=776677887;
    arr[598]=776767877;
    arr[599]=776787876;
    arr[600]=777656554;
    arr[601]=777667888;
    arr[602]=777765665;
    arr[603]=777777778;
    arr[604]=777876556;
    arr[605]=777888777;
    arr[606]=778766566;
    arr[607]=778778766;
    arr[608]=778876765;
    arr[609]=778888987;
    arr[610]=778988999;
    arr[611]=787655676;
    arr[612]=787667788;
    arr[613]=787765565;
    arr[614]=787777678;
    arr[615]=787789999;
    arr[616]=787887898;
    arr[617]=788766544;
    arr[618]=788777887;
    arr[619]=788876665;
    arr[620]=788888878;
    arr[621]=788988898;
    arr[622]=789877876;
    arr[623]=789898876;
    arr[624]=789998888;
    arr[625]=876545676;
    arr[626]=876565566;
    arr[627]=876655543;
    arr[628]=876667655;
    arr[629]=876765432;
    arr[630]=876776767;
    arr[631]=876788989;
    arr[632]=877665443;
    arr[633]=877676778;
    arr[634]=877766776;
    arr[635]=877778898;
    arr[636]=877877667;
    arr[637]=877889988;
    arr[638]=878767677;
    arr[639]=878787676;
    arr[640]=878877876;
    arr[641]=878898876;
    arr[642]=878998888;
    arr[643]=887656787;
    arr[644]=887676678;
    arr[645]=887766676;
    arr[646]=887778876;
    arr[647]=887876789;
    arr[648]=887889887;
    arr[649]=888767655;
    arr[650]=888787654;
    arr[651]=888877776;
    arr[652]=888898776;
    arr[653]=888998788;
    arr[654]=889878989;
    arr[655]=889987655;
    arr[656]=898765445;
    arr[657]=898776788;
    arr[658]=898789878;
    arr[659]=898887778;
    arr[660]=898987876;
    arr[661]=899876777;
    arr[662]=899888999;
    arr[663]=899989887;
    arr[664]=987656544;
    arr[665]=987667878;
    arr[666]=987765655;
    arr[667]=987777776;
    arr[668]=987876554;
    arr[669]=987888767;
    arr[670]=988766556;
    arr[671]=988777899;
    arr[672]=988876677;
    arr[673]=988888898;
    arr[674]=988988989;
    arr[675]=989877888;
    arr[676]=989898888;
    arr[677]=989998987;
    arr[678]=998776545;
    arr[679]=998788766;
    arr[680]=998878888;
    arr[681]=998899987;
    arr[682]=998999999;
    arr[683]=999887898;
    arr[684]=999988767;
    arr[685]=1000001232;
    arr[686]=1000110001;
    arr[687]=1000122322;
    arr[688]=1001011222;
    arr[689]=1001111234;
    arr[690]=1001123455;
    arr[691]=1001222233;
    arr[692]=1001234432;
    arr[693]=1010012222;
    arr[694]=1010112234;
    arr[695]=1011001010;
    arr[696]=1011101101;
    arr[697]=1011122101;
    arr[698]=1011212223;
    arr[699]=1011232222;
    arr[700]=1012101232;
    arr[701]=1012122232;
    arr[702]=1012221000;
    arr[703]=1012232345;
    arr[704]=1012322343;
    arr[705]=1012334456;
    arr[706]=1100000112;
    arr[707]=1100101000;
    arr[708]=1100121222;
    arr[709]=1101010110;
    arr[710]=1101110122;
    arr[711]=1101123212;
    arr[712]=1101221211;
    arr[713]=1101233333;
    arr[714]=1110011122;
    arr[715]=1110111212;
    arr[716]=1110123433;
    arr[717]=1111012334;
    arr[718]=1111121000;
    arr[719]=1111211123;
    arr[720]=1111223344;
    arr[721]=1112100112;
    arr[722]=1112121210;
    arr[723]=1112212111;
    arr[724]=1112232110;
    arr[725]=1112322100;
    arr[726]=1112333443;
    arr[727]=1112345555;
    arr[728]=1121012234;
    arr[729]=1121112332;
    arr[730]=1121211101;
    arr[731]=1121223322;
    arr[732]=1122100011;
    arr[733]=1122121110;
    arr[734]=1122211232;
    arr[735]=1122223445;
    arr[736]=1122321221;
    arr[737]=1122333343;
    arr[738]=1122345455;
    arr[739]=1123221232;
    arr[740]=1123233432;
    arr[741]=1123323344;
    arr[742]=1123343321;
    arr[743]=1123433212;
    arr[744]=1123444554;
    arr[745]=1123456666;
    arr[746]=1210012234;
    arr[747]=1210112332;
    arr[748]=1211001101;
    arr[749]=1211101121;
    arr[750]=1211122121;
    arr[751]=1211212321;
    arr[752]=1211232234;
    arr[753]=1212110001;
    arr[754]=1212122322;
    arr[755]=1212221012;
    arr[756]=1212233221;
    arr[757]=1212323211;
    arr[758]=1212334554;
    arr[759]=1221001000;
    arr[760]=1221101012;
    arr[761]=1221121234;
    arr[762]=1221212221;
    arr[763]=1221232212;
    arr[764]=1222101222;
    arr[765]=1222122222;
    arr[766]=1222212344;
    arr[767]=1222232343;
    arr[768]=1222322333;
    arr[769]=1222334454;
    arr[770]=1223210110;
    arr[771]=1223222344;
    arr[772]=1223234543;
    arr[773]=1223332234;
    arr[774]=1223344432;
    arr[775]=1223434323;
    arr[776]=1223445665;
    arr[777]=1232101000;
    arr[778]=1232121222;
    arr[779]=1232212123;
    arr[780]=1232232122;
    arr[781]=1232322112;
    arr[782]=1232333455;
    arr[783]=1232345567;
    arr[784]=1233222123;
    arr[785]=1233234322;
    arr[786]=1233323456;
    arr[787]=1233343433;
    arr[788]=1233433332;
    arr[789]=1233445444;
    arr[790]=1233456778;
    arr[791]=1234332333;
    arr[792]=1234344445;
    arr[793]=1234434344;
    arr[794]=1234445678;
    arr[795]=1234543432;
    arr[796]=1234555544;
    arr[797]=1234567656;
    arr[798]=2100012122;
    arr[799]=2100112212;
    arr[800]=2101000112;
    arr[801]=2101101000;
    arr[802]=2101121222;
    arr[803]=2101212123;
    arr[804]=2101232122;
    arr[805]=2110001210;
    arr[806]=2110101222;
    arr[807]=2110122222;
    arr[808]=2111011122;
    arr[809]=2111111212;
    arr[810]=2111123433;
    arr[811]=2111222211;
    arr[812]=2111234332;
    arr[813]=2112112122;
    arr[814]=2112210100;
    arr[815]=2112222334;
    arr[816]=2112234455;
    arr[817]=2112332232;
    arr[818]=2112344344;
    arr[819]=2121011100;
    arr[820]=2121111112;
    arr[821]=2121123333;
    arr[822]=2121222111;
    arr[823]=2121233454;
    arr[824]=2122112100;
    arr[825]=2122123456;
    arr[826]=2122222234;
    arr[827]=2122234433;
    arr[828]=2122332210;
    arr[829]=2122344322;
    arr[830]=2123212222;
    arr[831]=2123232221;
    arr[832]=2123322211;
    arr[833]=2123334332;
    arr[834]=2123345666;
    arr[835]=2123443343;
    arr[836]=2123455455;
    arr[837]=2210011100;
    arr[838]=2210111112;
    arr[839]=2210123333;
    arr[840]=2211012234;
    arr[841]=2211112332;
    arr[842]=2211211101;
    arr[843]=2211223322;
    arr[844]=2212100011;
    arr[845]=2212121110;
    arr[846]=2212211232;
    arr[847]=2212223445;
    arr[848]=2212321221;
    arr[849]=2212333343;
    arr[850]=2212345455;
    arr[851]=2221012212;
    arr[852]=2221112232;
    arr[853]=2221211000;
    arr[854]=2221223222;
    arr[855]=2221234565;
    arr[856]=2222121001;
    arr[857]=2222211210;
    arr[858]=2222223345;
    arr[859]=2222321121;
    arr[860]=2222333321;
    arr[861]=2222345433;
    arr[862]=2223221210;
    arr[863]=2223233332;
    arr[864]=2223323322;
    arr[865]=2223343221;
    arr[866]=2223432334;
    arr[867]=2223444454;
    arr[868]=2223456566;
    arr[869]=2232112212;
    arr[870]=2232210112;
    arr[871]=2232223210;
    arr[872]=2232234545;
    arr[873]=2232332322;
    arr[874]=2232344434;
    arr[875]=2233212334;
    arr[876]=2233232333;
    arr[877]=2233322323;
    arr[878]=2233334444;
    arr[879]=2233432121;
    arr[880]=2233443455;
    arr[881]=2233455567;
    arr[882]=2234323343;
    arr[883]=2234343234;
    arr[884]=2234433211;
    arr[885]=2234444545;
    arr[886]=2234456665;
    arr[887]=2234554333;
    arr[888]=2234565667;
    arr[889]=2321010111;
    arr[890]=2321110123;
    arr[891]=2321123221;
    arr[892]=2321221212;
    arr[893]=2321233334;
    arr[894]=2322111123;
    arr[895]=2322123344;
    arr[896]=2322222122;
    arr[897]=2322234321;
    arr[898]=2322323455;
    arr[899]=2322343432;
    arr[900]=2323212110;
    arr[901]=2323232101;
    arr[902]=2323321234;
    arr[903]=2323333434;
    arr[904]=2323345554;
    arr[905]=2323443223;
    arr[906]=2323454565;
    arr[907]=2332110111;
    arr[908]=2332122345;
    arr[909]=2332221122;
    arr[910]=2332233322;
    arr[911]=2332323234;
    arr[912]=2332343211;
    arr[913]=2333211110;
    arr[914]=2333223323;
    arr[915]=2333321012;
    arr[916]=2333333221;
    arr[917]=2333344555;
    arr[918]=2333434454;
    arr[919]=2333454344;
    arr[920]=2334322112;
    arr[921]=2334333455;
    arr[922]=2334345567;
    arr[923]=2334443322;
    arr[924]=2334455434;
    arr[925]=2334544554;
    arr[926]=2334556666;
    arr[927]=2343210101;
    arr[928]=2343222343;
    arr[929]=2343234456;
    arr[930]=2343332233;
    arr[931]=2343344345;
    arr[932]=2343434322;
    arr[933]=2343445656;
    arr[934]=2344321123;
    arr[935]=2344333323;
    arr[936]=2344345443;
    arr[937]=2344434556;
    arr[938]=2344454454;
    arr[939]=2344544344;
    arr[940]=2344555678;
    arr[941]=2344567876;
    arr[942]=2345443332;
    arr[943]=2345455444;
    arr[944]=2345544556;
    arr[945]=2345556676;
    arr[946]=2345654345;
    arr[947]=2345666543;
    arr[948]=2345677878;
    arr[949]=3210012110;
    arr[950]=3210112122;
    arr[951]=3211000100;
    arr[952]=3211100112;
    arr[953]=3211121210;
    arr[954]=3211212111;
    arr[955]=3211232110;
    arr[956]=3212101112;
    arr[957]=3212122112;
    arr[958]=3212212234;
    arr[959]=3212232233;
    arr[960]=3212322223;
    arr[961]=3212334344;
    arr[962]=3212345678;
    arr[963]=3221100011;
    arr[964]=3221121110;
    arr[965]=3221211232;
    arr[966]=3221223445;
    arr[967]=3222101011;
    arr[968]=3222121233;
    arr[969]=3222212212;
    arr[970]=3222232211;
    arr[971]=3222322123;
    arr[972]=3222334322;
    arr[973]=3222345656;
    arr[974]=3223222212;
    arr[975]=3223234333;
    arr[976]=3223332110;
    arr[977]=3223343444;
    arr[978]=3223433343;
    arr[979]=3223445455;
    arr[980]=3223456789;
    arr[981]=3232121011;
    arr[982]=3232211212;
    arr[983]=3232223433;
    arr[984]=3232321123;
    arr[985]=3232333323;
    arr[986]=3232345443;
    arr[987]=3233221212;
    arr[988]=3233233334;
    arr[989]=3233323332;
    arr[990]=3233343223;
    arr[991]=3233432344;
    arr[992]=3233444456;
    arr[993]=3233456654;
    arr[994]=3234332123;
    arr[995]=3234344321;
    arr[996]=3234433434;
    arr[997]=3234445554;
    arr[998]=3234543222;
    arr[999]=3234554556;

}
void solve(){
    precalc();
    /*ll n=3234566667+1;
    int now=1;
    for(ll i=1;i<n;i++){
        if(lol(i)){
            if((now-1)%100==0){
                arr.pb(i);
            }
            now++;
        }
    }
    for(int i=1;i<arr.size()+1;i++){
        cout<<"arr["<<i-1<<"]="<<arr[i-1]<<";"<<endl;
    }*/
    int k;
    cin>>k;
    int ind=-1;
    for(int i=0;i<arr.size();i++){
        int now=i*100+1;
        if(now>k){
            ind=i-1;
            k-=(i-1)*100+1;
            break;
        }
    }
    if(ind==-1){
        k-=(arr.size()-1)*100+1;
        ind=arr.size()-1;
    }
    ll i,kolvo;
    for(i=arr[ind], kolvo=0;kolvo<=k;i++){
        if(lol(i)){
            kolvo++;
        }
    }
    cout<<i-1<<endl;
}



void testcases(int n) {
    n = 1 - n;
    if (!n) cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "r", stdin);
    //f=fopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w");
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w", stdout);

    unsigned int beg_time = clock();
    testcases(0);
    // 0 - no t, 1 - with t

    unsigned int end_time = clock();
    //cout << endl << endl << end_time - beg_time;
    return 0;
}

Measured memory_bytes: 256