const opt1 = () => {
  let max = 0;
  const next = n => {
    let cnt = 1;
    while (1) {
      const str = cnt++ + (n + '');
      const bi = BigInt(str);
      const mod = BigInt('1' + '0'.repeat(str.length));
      // const pow = (bi * bi) + '';
      // const idx = pow.indexOf(str, str.length/2-2);
      if (bi * bi % mod === bi) {
        if (cnt > max) max = cnt;
        return bi;
      }
    }
  };

  const arr = [1n];
  let n1 = 5n;
  let n2 = 6n;

  const t = +new Date();
  while (1) {
    if (n1 < n2) {
      arr.push(n1);
      n1 = next(n1);
    } else {
      arr.push(n2);
      n2 = next(n2);
    }
    if (arr.length >= 4e3) break;
    const l = arr[arr.length-1];
    // console.log(arr.length, l);
  }
  // console.log(+new Date() - t);
  // console.log((arr[arr.length-1]+'').length);

  // console.log('max inc', max);
  // console.log(arr.slice(-10).map((n, i) => [i, (n+'')]));
  const green = n => arr[n];
  return arr;
};


const opt2 = () => {
  
  const next = (n, c) => {
    while (1) {
      if (n[c] === '0') {
        ++c;
        continue;
      }
      const str = n.slice(++c);
      if (str.length === 0) return [null, null];
      const bi = BigInt(str);
      const mod = BigInt('1' + '0'.repeat(str.length));
      // if (bi * bi % mod === bi) {
        return [bi, c];
      // }
    }
  };
  
  // 3999
  const n625 = '28882689374022112371252012273120606174751574751537381989074240665252066611148827637678947177773960015235903946894098140630385847547907319150251760258945788659491966429549908540773478285449868640866567399269578082162283572603026954569487924380165488488051064862760620827164159132523609790500938385405426324719893931802209823600162545177681029159396504506657809033052772198385286341879645511424748536307235457049044509125214234275955491843973984458712528694819826927029255264834903206526851272202961318699947776535481291519857640422968183091773445277723200737603825883172729279563657419014445235954319103063572496178988203175787761062137708080967811374931911766563031490205784352509572880668464121069252802275061298511616206384006778979402449023875111258689534549514888200678667702341002839549282970286447273625217535443197911855068157264858804852673871684804002188529473022223344541221328464844153593793663133604458940328723478401947357560361346212008675373346913314338717350880212600285752985386643931022326553454776845029957025561658143370236502074744856814787872902092412582905301249124668868351587677499891768678715728134940879276894529797097772305403356618828198702210630557967239806611190197744642421025136748701117131278125400133690086034889084364023875765936821979626181917833520492704199324875237825867148278905344897440142612317035699548419499444610608146207254036559998271588356035049327795540741961849280952093753026852390937562839148571612367351970609224242398777007574955787271559767413458997537695515862718887941516307569668816352155048898271704378508028434084412644126821848514157729916034497017892335796684991447389566001932545827678000618329854426232827257556110733160697015864984222291255485729879337147866323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625';
  // 4000
  const n376 = '71117310625977887628747987726879393825248425248462618010925759334747933388851172362321052822226039984764096053105901859369614152452092680849748239741054211340508033570450091459226521714550131359133432600730421917837716427396973045430512075619834511511948935137239379172835840867476390209499061614594573675280106068197790176399837454822318970840603495493342190966947227801614713658120354488575251463692764542950955490874785765724044508156026015541287471305180173072970744735165096793473148727797038681300052223464518708480142359577031816908226554722276799262396174116827270720436342580985554764045680896936427503821011796824212238937862291919032188625068088233436968509794215647490427119331535878930747197724938701488383793615993221020597550976124888741310465450485111799321332297658997160450717029713552726374782464556802088144931842735141195147326128315195997811470526977776655458778671535155846406206336866395541059671276521598052642439638653787991324626653086685661282649119787399714247014613356068977673446545223154970042974438341856629763497925255143185212127097907587417094698750875331131648412322500108231321284271865059120723105470202902227694596643381171801297789369442032760193388809802255357578974863251298882868721874599866309913965110915635976124234063178020373818082166479507295800675124762174132851721094655102559857387682964300451580500555389391853792745963440001728411643964950672204459258038150719047906246973147609062437160851428387632648029390775757601222992425044212728440232586541002462304484137281112058483692430331183647844951101728295621491971565915587355873178151485842270083965502982107664203315008552610433998067454172321999381670145573767172742443889266839302984135015777708744514270120662852133676827594484243897647456005000654391916198809258469939943944255181290307214900224081949924583571472291837988649753193941836723828323234739062471943155785513806039500165527193278093329582759905765533802187573309212464055383301491935363862833615950970780658118090418340475522138153859087121701561568296751826571113427262336853480895011970552039185326239496042803106285328198624380944537003185235736096046992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376';
  
  const arr = [1n];
  let [c625, c376] = [0, 0];
  let cnt = 4000 - 1;
  let n1 = BigInt(n625);
  let n2 = BigInt(n376);
  
  while (cnt > 0) {
    if (n1 > n2) {
      arr[cnt] = n1;
      [n1, c625] = next(n625, c625);
    } else {
      arr[cnt] = n2;
      [n2, c376] = next(n376, c376);
    }
    // console.log(c625, c376)
    
    --cnt;
  }
  
  return arr;
};

const t1 = +new Date();
const arr2 = opt2();
const t2 = +new Date();
const arr1 = opt1();
const t3 = +new Date();

console.log('opt 1: ', t2-t1);
console.log('opt 2: ', t3-t2);

console.log(arr1.length, arr2.length);

let fcnt = 0;
for (let i = 0; i < arr1.length; ++i) {
  if (arr1[i] !== arr2[i]) {
    ++fcnt;
    console.log('FAILED');
  }
}

console.log('done', fcnt, 'failed');