--- title: Ethash description: "Podrobný pohled na algoritmus Ethash." lang: cs --- Ethash byl těžební algoritmus Etherea založený na důkazu prací (PoW). Důkaz prací (PoW) byl nyní **zcela vypnut** a Ethereum je místo toho zabezpečeno pomocí [důkazu podílem (PoS)](/developers/docs/consensus-mechanisms/pos/). Přečtěte si více o [Merge](/roadmap/merge/), [důkazu podílem (PoS)](/developers/docs/consensus-mechanisms/pos/) a [stakingu](/staking/). Tato stránka slouží pouze pro historické účely! Ethash je upravená verze algoritmu [Dagger-Hashimoto](/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms/dagger-hashimoto). Důkaz prací (PoW) Ethash je [paměťově náročný](https://wikipedia.org/wiki/Memory-hard_function), což mělo zajistit odolnost algoritmu vůči ASIC. ASIC pro Ethash byly nakonec vyvinuty, ale těžba pomocí GPU byla stále schůdnou možností, dokud nebyl důkaz prací (PoW) vypnut. Ethash se stále používá k těžbě jiných mincí na jiných sítích s důkazem prací (PoW) mimo Ethereum. ## Jak Ethash funguje? {#how-does-ethash-work} Paměťové náročnosti je dosaženo pomocí algoritmu důkazu prací (PoW), který vyžaduje výběr podmnožin pevného zdroje v závislosti na nonce a hlavičce bloku. Tento zdroj (o velikosti několika gigabajtů) se nazývá DAG. DAG se mění každých 30 000 bloků, což je okno o délce přibližně 125 hodin nazývané epocha (zhruba 5,2 dne), a jeho generování chvíli trvá. Vzhledem k tomu, že DAG závisí pouze na výšce bloku, může být předgenerován, ale pokud není, klient musí počkat na konec tohoto procesu, aby mohl vytvořit blok. Pokud klienti předem negenerují a neukládají DAG do mezipaměti, síť může při každém přechodu epochy zaznamenat masivní zpoždění bloků. Všimněte si, že DAG není nutné generovat pro ověření důkazu prací (PoW), což v podstatě umožňuje ověření s nízkým využitím CPU i malou pamětí. Obecný postup algoritmu je následující: 1. Existuje **seed** (semínko), které lze vypočítat pro každý blok prohledáním hlaviček bloků až do daného bodu. 2. Ze seedu lze vypočítat **16 MB pseudonáhodnou mezipaměť (cache)**. Lehcí klienti (light clients) tuto mezipaměť ukládají. 3. Z mezipaměti můžeme vygenerovat **1 GB datovou sadu (dataset)** s tou vlastností, že každá položka v datové sadě závisí pouze na malém počtu položek z mezipaměti. Plní klienti (full clients) a těžaři tuto datovou sadu ukládají. Datová sada roste lineárně s časem. 4. Těžba zahrnuje odebírání náhodných částí datové sady a jejich společné hashování. Ověření lze provést s nízkou pamětí pomocí mezipaměti k opětovnému vygenerování konkrétních částí datové sady, které potřebujete, takže stačí ukládat pouze mezipaměť. Velká datová sada se aktualizuje jednou za 30 000 bloků, takže drtivá většina úsilí těžaře bude spočívat ve čtení datové sady, nikoli v jejích úpravách. ## Definice {#definitions} Používáme následující definice: ``` WORD_BYTES = 4 # bajtů ve slově DATASET_BYTES_INIT = 2**30 # bajtů v datové sadě při genesis DATASET_BYTES_GROWTH = 2**23 # růst datové sady za epochu CACHE_BYTES_INIT = 2**24 # bajtů v mezipaměti při genesis CACHE_BYTES_GROWTH = 2**17 # růst mezipaměti za epochu CACHE_MULTIPLIER=1024 # Velikost DAG vzhledem k mezipaměti EPOCH_LENGTH = 30000 # bloků za epochu MIX_BYTES = 128 # šířka mixu HASH_BYTES = 64 # délka hashe v bajtech DATASET_PARENTS = 256 # počet rodičů každého prvku datové sady CACHE_ROUNDS = 3 # počet kol při tvorbě mezipaměti ACCESSES = 64 # počet přístupů ve smyčce hashimoto ``` ### Použití 'SHA3' {#sha3} Vývoj Etherea se časově shodoval s vývojem standardu SHA3 a proces standardizace provedl pozdní změnu ve výplni (padding) finalizovaného hashovacího algoritmu, takže hashe „sha3_256“ a „sha3_512“ v Ethereu nejsou standardní hashe sha3, ale varianta často označovaná v jiných kontextech jako „Keccak-256“ a „Keccak-512“. Viz diskuse, např. [zde](https://eips.ethereum.org/EIPS/eip-1803), [zde](https://ethereum.stackexchange.com/questions/550/which-cryptographic-hash-function-does-ethereum-use) nebo [zde](https://bitcoin.stackexchange.com/questions/42055/what-is-the-approach-to-calculate-an-ethereum-address-from-a-256-bit-private-key/42057#42057). Mějte to prosím na paměti, protože v níže uvedeném popisu algoritmu se odkazuje na hashe „sha3“. ## Parametry {#parameters} Parametry pro mezipaměť a datovou sadu Ethash závisí na čísle bloku. Velikost mezipaměti i velikost datové sady rostou lineárně; vždy však bereme nejvyšší prvočíslo pod lineárně rostoucí prahovou hodnotou, abychom snížili riziko náhodných pravidelností vedoucích k cyklickému chování. ```python def get_cache_size(block_number): sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH) sz -= HASH_BYTES while not isprime(sz / HASH_BYTES): sz -= 2 * HASH_BYTES return sz def get_full_size(block_number): sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH) sz -= MIX_BYTES while not isprime(sz / MIX_BYTES): sz -= 2 * MIX_BYTES return sz ``` Tabulky hodnot velikostí datové sady a mezipaměti jsou uvedeny v příloze. ## Generování mezipaměti {#cache-generation} Nyní specifikujeme funkci pro vytvoření mezipaměti: ```python def mkcache(cache_size, seed): n = cache_size // HASH_BYTES # Sekvenčně vytvořit počáteční datovou sadu o = [sha3_512(seed)] for i in range(1, n): o.append(sha3_512(o[-1])) # Použít verzi randmemohash s nízkým počtem kol for _ in range(CACHE_ROUNDS): for i in range(n): v = o[i][0] % n o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v])) return o ``` Proces tvorby mezipaměti zahrnuje nejprve sekvenční zaplnění 32 MB paměti a poté provedení dvou průchodů algoritmu _RandMemoHash_ od Sergia Demiana Lernera z [_Strict Memory Hard Hashing Functions_ (2014)](http://www.hashcash.org/papers/memohash.pdf). Výstupem je sada 524 288 64bajtových hodnot. ## Funkce agregace dat {#date-aggregation-function} V některých případech používáme algoritmus inspirovaný [FNV hashem](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function) jako neasociativní náhradu za XOR. Všimněte si, že prvočíslo násobíme celým 32bitovým vstupem, na rozdíl od specifikace FNV-1, která násobí prvočíslo postupně jedním bajtem (oktetem). ```python FNV_PRIME = 0x01000193 def fnv(v1, v2): return ((v1 * FNV_PRIME) ^ v2) % 2**32 ``` Vezměte prosím na vědomí, že i když yellow paper specifikuje fnv jako v1\*(FNV_PRIME ^ v2), všechny současné implementace konzistentně používají výše uvedenou definici. ## Výpočet celé datové sady {#full-dataset-calculation} Každá 64bajtová položka v celé 1 GB datové sadě se vypočítá následovně: ```python def calc_dataset_item(cache, i): n = len(cache) r = HASH_BYTES // WORD_BYTES # inicializovat mix mix = copy.copy(cache[i % n]) mix[0] ^= i mix = sha3_512(mix) # aplikovat na to fnv s mnoha náhodnými uzly cache na základě i for j in range(DATASET_PARENTS): cache_index = fnv(i ^ j, mix[j % r]) mix = map(fnv, mix, cache[cache_index % n]) return sha3_512(mix) ``` V podstatě kombinujeme data z 256 pseudonáhodně vybraných uzlů mezipaměti a hashujeme je, abychom vypočítali uzel datové sady. Celá datová sada je pak generována pomocí: ```python def calc_dataset(full_size, cache): return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)] ``` ## Hlavní smyčka {#main-loop} Nyní specifikujeme hlavní smyčku podobnou „hashimoto“, kde agregujeme data z celé datové sady, abychom vytvořili naši konečnou hodnotu pro konkrétní hlavičku a nonce. V níže uvedeném kódu představuje `header` SHA3-256 _hash_ RLP reprezentace _zkrácené_ hlavičky bloku, tedy hlavičky bez polí **mixHash** a **nonce**. `nonce` je osm bajtů 64bitového celého čísla bez znaménka v pořadí big-endian. Takže `nonce[::-1]` je osmi-bajtová little-endian reprezentace této hodnoty: ```python def hashimoto(header, nonce, full_size, dataset_lookup): n = full_size / HASH_BYTES w = MIX_BYTES // WORD_BYTES mixhashes = MIX_BYTES / HASH_BYTES # zkombinovat hlavičku+nonce do 64bajtového seedu s = sha3_512(header + nonce[::-1]) # začít mix s replikovaným s mix = [] for _ in range(MIX_BYTES / HASH_BYTES): mix.extend(s) # přimíchat náhodné uzly datové sady for i in range(ACCESSES): p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes newdata = [] for j in range(MIX_BYTES / HASH_BYTES): newdata.extend(dataset_lookup(p + j)) mix = map(fnv, mix, newdata) # zkomprimovat mix cmix = [] for i in range(0, len(mix), 4): cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])) return { "mix digest": serialize_hash(cmix), "result": serialize_hash(sha3_256(s+cmix)) } def hashimoto_light(full_size, cache, header, nonce): return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x)) def hashimoto_full(full_size, dataset, header, nonce): return hashimoto(header, nonce, full_size, lambda x: dataset[x]) ``` V podstatě udržujeme „mix“ o šířce 128 bajtů a opakovaně sekvenčně načítáme 128 bajtů z celé datové sady a používáme funkci `fnv` k jejich kombinaci s mixem. Používá se 128 bajtů sekvenčního přístupu, aby každé kolo algoritmu vždy načetlo celou stránku z RAM, čímž se minimalizují výpadky v translation lookaside bufferu (TLB), kterým by se ASIC teoreticky dokázaly vyhnout. Pokud je výstup tohoto algoritmu pod požadovaným cílem, pak je nonce platná. Všimněte si, že dodatečná aplikace `sha3_256` na konci zajišťuje, že existuje zprostředkující nonce, kterou lze poskytnout jako důkaz, že bylo vykonáno alespoň malé množství práce; toto rychlé vnější ověření PoW lze použít pro účely ochrany proti DDoS. Slouží také k poskytnutí statistické jistoty, že výsledek je nezkreslené 256bitové číslo. ## Těžba {#mining} Algoritmus těžby je definován následovně: ```python def mine(full_size, dataset, header, difficulty): # doplnit cíl nulami pro porovnání s hashem na stejné číslici target = zpad(encode_int(2**256 // difficulty), 64)[::-1] from random import randint nonce = randint(0, 2**64) while hashimoto_full(full_size, dataset, header, nonce) > target: nonce = (nonce + 1) % 2**64 return nonce ``` ## Definování seed hashe {#seed-hash} Pro výpočet seed hashe, který by se použil k těžbě na vrcholu daného bloku, používáme následující algoritmus: ```python def get_seedhash(block): s = '\x00' * 32 for i in range(block.number // EPOCH_LENGTH): s = serialize_hash(sha3_256(s)) return s ``` Všimněte si, že pro plynulou těžbu a ověřování doporučujeme předem vypočítat budoucí seed hashe a datové sady v samostatném vlákně. ## Další čtení {#further-reading} _Víte o komunitním zdroji, který vám pomohl? Upravte tuto stránku a přidejte ho!_ ## Příloha {#appendix} Následující kód by měl být přidán na začátek, pokud máte zájem spustit výše uvedenou specifikaci v Pythonu jako kód. ```python import sha3, copy # Předpokládá uspořádání bitů little-endian (stejné jako u architektur Intel) def decode_int(s): return int(s[::-1].encode('hex'), 16) if s else 0 def encode_int(s): a = "%x" % s return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1] def zpad(s, length): return s + '\x00' * max(0, length - len(s)) def serialize_hash(h): return ''.join([zpad(encode_int(x), 4) for x in h]) def deserialize_hash(h): return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)] def hash_words(h, sz, x): if isinstance(x, list): x = serialize_hash(x) y = h(x) return deserialize_hash(y) def serialize_cache(ds): return ''.join([serialize_hash(h) for h in ds]) serialize_dataset = serialize_cache # hashovací funkce sha3, výstup 64 bajtů def sha3_512(x): return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x) def sha3_256(x): return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x) def xor(a, b): return a ^ b def isprime(x): for i in range(2, int(x**0.5)): if x % i == 0: return False return True ``` ### Velikosti dat {#data-sizes} Následující vyhledávací tabulky poskytují přibližně 2048 tabelovaných epoch velikostí dat a velikostí mezipaměti. ```python def get_datasize(block_number): return data_sizes[block_number // EPOCH_LENGTH] def get_cachesize(block_number): return cache_sizes[block_number // EPOCH_LENGTH] data_sizes = [ 1073739904, 1082130304, 1090514816, 1098906752, 1107293056, 1115684224, 1124070016, 1132461952, 1140849536, 1149232768, 1157627776, 1166013824, 1174404736, 1182786944, 1191180416, 1199568512, 1207958912, 1216345216, 1224732032, 1233124736, 1241513344, 1249902464, 1258290304, 1266673792, 1275067264, 1283453312, 1291844992, 1300234112, 1308619904, 1317010048, 1325397376, 1333787776, 1342176128, 1350561664, 1358954368, 1367339392, 1375731584, 1384118144, 1392507008, 1400897408, 1409284736, 1417673344, 1426062464, 1434451072, 1442839168, 1451229056, 1459615616, 1468006016, 1476394112, 1484782976, 1493171584, 1501559168, 1509948032, 1518337664, 1526726528, 1535114624, 1543503488, 1551892096, 1560278656, 1568669056, 1577056384, 1585446272, 1593831296, 1602219392, 1610610304, 1619000192, 1627386752, 1635773824, 1644164224, 1652555648, 1660943488, 1669332608, 1677721216, 1686109312, 1694497664, 1702886272, 1711274624, 1719661184, 1728047744, 1736434816, 1744829056, 1753218944, 1761606272, 1769995904, 1778382464, 1786772864, 1795157888, 1803550592, 1811937664, 1820327552, 1828711552, 1837102976, 1845488768, 1853879936, 1862269312, 1870656896, 1879048064, 1887431552, 1895825024, 1904212096, 1912601216, 1920988544, 1929379456, 1937765504, 1946156672, 1954543232, 1962932096, 1971321728, 1979707264, 1988093056, 1996487552, 2004874624, 2013262208, 2021653888, 2030039936, 2038430848, 2046819968, 2055208576, 2063596672, 2071981952, 2080373632, 2088762752, 2097149056, 2105539712, 2113928576, 2122315136, 2130700672, 2139092608, 2147483264, 2155872128, 2164257664, 2172642176, 2181035392, 2189426048, 2197814912, 2206203008, 2214587264, 2222979712, 2231367808, 2239758208, 2248145024, 2256527744, 2264922752, 2273312128, 2281701248, 2290086272, 2298476672, 2306867072, 2315251072, 2323639168, 2332032128, 2340420224, 2348808064, 2357196416, 2365580416, 2373966976, 2382363008, 2390748544, 2399139968, 2407530368, 2415918976, 2424307328, 2432695424, 2441084288, 2449472384, 2457861248, 2466247808, 2474637184, 2483026816, 2491414144, 2499803776, 2508191872, 2516582272, 2524970368, 2533359232, 2541743488, 2550134144, 2558525056, 2566913408, 2575301504, 2583686528, 2592073856, 2600467328, 2608856192, 2617240448, 2625631616, 2634022016, 2642407552, 2650796416, 2659188352, 2667574912, 2675965312, 2684352896, 2692738688, 2701130624, 2709518464, 2717907328, 2726293376, 2734685056, 2743073152, 2751462016, 2759851648, 2768232832, 2776625536, 2785017728, 2793401984, 2801794432, 2810182016, 2818571648, 2826959488, 2835349376, 2843734144, 2852121472, 2860514432, 2868900992, 2877286784, 2885676928, 2894069632, 2902451584, 2910843008, 2919234688, 2927622784, 2936011648, 2944400768, 2952789376, 2961177728, 2969565568, 2977951616, 2986338944, 2994731392, 3003120256, 3011508352, 3019895936, 3028287104, 3036675968, 3045063808, 3053452928, 3061837696, 3070228352, 3078615424, 3087003776, 3095394944, 3103782272, 3112173184, 3120562048, 3128944768, 3137339264, 3145725056, 3154109312, 3162505088, 3170893184, 3179280256, 3187669376, 3196056704, 3204445568, 3212836736, 3221224064, 3229612928, 3238002304, 3246391168, 3254778496, 3263165824, 3271556224, 3279944576, 3288332416, 3296719232, 3305110912, 3313500032, 3321887104, 3330273152, 3338658944, 3347053184, 3355440512, 3363827072, 3372220288, 3380608384, 3388997504, 3397384576, 3405774208, 3414163072, 3422551936, 3430937984, 3439328384, 3447714176, 3456104576, 3464493952, 3472883584, 3481268864, 3489655168, 3498048896, 3506434432, 3514826368, 3523213952, 3531603584, 3539987072, 3548380288, 3556763264, 3565157248, 3573545344, 3581934464, 3590324096, 3598712704, 3607098752, 3615488384, 3623877248, 3632265856, 3640646528, 3649043584, 3657430144, 3665821568, 3674207872, 3682597504, 3690984832, 3699367808, 3707764352, 3716152448, 3724541056, 3732925568, 3741318016, 3749706368, 3758091136, 3766481536, 3774872704, 3783260032, 3791650432, 3800036224, 3808427648, 3816815488, 3825204608, 3833592704, 3841981568, 3850370432, 3858755968, 3867147904, 3875536256, 3883920512, 3892313728, 3900702592, 3909087872, 3917478784, 3925868416, 3934256512, 3942645376, 3951032192, 3959422336, 3967809152, 3976200064, 3984588416, 3992974976, 4001363584, 4009751168, 4018141312, 4026530432, 4034911616, 4043308928, 4051695488, 4060084352, 4068472448, 4076862848, 4085249408, 4093640576, 4102028416, 4110413696, 4118805632, 4127194496, 4135583104, 4143971968, 4152360832, 4160746112, 4169135744, 4177525888, 4185912704, 4194303616, 4202691968, 4211076736, 4219463552, 4227855488, 4236246656, 4244633728, 4253022848, 4261412224, 4269799808, 4278184832, 4286578048, 4294962304, 4303349632, 4311743104, 4320130432, 4328521088, 4336909184, 4345295488, 4353687424, 4362073472, 4370458496, 4378852736, 4387238528, 4395630208, 4404019072, 4412407424, 4420790656, 4429182848, 4437571456, 4445962112, 4454344064, 4462738048, 4471119232, 4479516544, 4487904128, 4496289664, 4504682368, 4513068416, 4521459584, 4529846144, 4538232704, 4546619776, 4555010176, 4563402112, 4571790208, 4580174464, 4588567936, 4596957056, 4605344896, 4613734016, 4622119808, 4630511488, 4638898816, 4647287936, 4655675264, 4664065664, 4672451968, 4680842624, 4689231488, 4697620352, 4706007424, 4714397056, 4722786176, 4731173248, 4739562368, 4747951744, 4756340608, 4764727936, 4773114496, 4781504384, 4789894784, 4798283648, 4806667648, 4815059584, 4823449472, 4831835776, 4840226176, 4848612224, 4857003392, 4865391488, 4873780096, 4882169728, 4890557312, 4898946944, 4907333248, 4915722368, 4924110976, 4932499328, 4940889728, 4949276032, 4957666432, 4966054784, 4974438016, 4982831488, 4991221376, 4999607168, 5007998848, 5016386432, 5024763776, 5033164672, 5041544576, 5049941888, 5058329728, 5066717056, 5075107456, 5083494272, 5091883904, 5100273536, 5108662144, 5117048192, 5125436032, 5133827456, 5142215296, 5150605184, 5158993024, 5167382144, 5175769472, 5184157568, 5192543872, 5200936064, 5209324928, 5217711232, 5226102656, 5234490496, 5242877312, 5251263872, 5259654016, 5268040832, 5276434304, 5284819328, 5293209728, 5301598592, 5309986688, 5318374784, 5326764416, 5335151488, 5343542144, 5351929472, 5360319872, 5368706944, 5377096576, 5385484928, 5393871232, 5402263424, 5410650496, 5419040384, 5427426944, 5435816576, 5444205952, 5452594816, 5460981376, 5469367936, 5477760896, 5486148736, 5494536832, 5502925952, 5511315328, 5519703424, 5528089984, 5536481152, 5544869504, 5553256064, 5561645696, 5570032768, 5578423936, 5586811264, 5595193216, 5603585408, 5611972736, 5620366208, 5628750464, 5637143936, 5645528192, 5653921408, 5662310272, 5670694784, 5679082624, 5687474048, 5695864448, 5704251008, 5712641408, 5721030272, 5729416832, 5737806208, 5746194304, 5754583936, 5762969984, 5771358592, 5779748224, 5788137856, 5796527488, 5804911232, 5813300608, 5821692544, 5830082176, 5838468992, 5846855552, 5855247488, 5863636096, 5872024448, 5880411008, 5888799872, 5897186432, 5905576832, 5913966976, 5922352768, 5930744704, 5939132288, 5947522432, 5955911296, 5964299392, 5972688256, 5981074304, 5989465472, 5997851008, 6006241408, 6014627968, 6023015552, 6031408256, 6039796096, 6048185216, 6056574848, 6064963456, 6073351808, 6081736064, 6090128768, 6098517632, 6106906496, 6115289216, 6123680896, 6132070016, 6140459648, 6148849024, 6157237376, 6165624704, 6174009728, 6182403712, 6190792064, 6199176064, 6207569792, 6215952256, 6224345216, 6232732544, 6241124224, 6249510272, 6257899136, 6266287744, 6274676864, 6283065728, 6291454336, 6299843456, 6308232064, 6316620928, 6325006208, 6333395584, 6341784704, 6350174848, 6358562176, 6366951296, 6375337856, 6383729536, 6392119168, 6400504192, 6408895616, 6417283456, 6425673344, 6434059136, 6442444672, 6450837376, 6459223424, 6467613056, 6476004224, 6484393088, 6492781952, 6501170048, 6509555072, 6517947008, 6526336384, 6534725504, 6543112832, 6551500672, 6559888768, 6568278656, 6576662912, 6585055616, 6593443456, 6601834112, 6610219648, 6618610304, 6626999168, 6635385472, 6643777408, 6652164224, 6660552832, 6668941952, 6677330048, 6685719424, 6694107776, 6702493568, 6710882176, 6719274112, 6727662976, 6736052096, 6744437632, 6752825984, 6761213824, 6769604224, 6777993856, 6786383488, 6794770816, 6803158144, 6811549312, 6819937664, 6828326528, 6836706176, 6845101696, 6853491328, 6861880448, 6870269312, 6878655104, 6887046272, 6895433344, 6903822208, 6912212864, 6920596864, 6928988288, 6937377152, 6945764992, 6954149248, 6962544256, 6970928768, 6979317376, 6987709312, 6996093824, 7004487296, 7012875392, 7021258624, 7029652352, 7038038912, 7046427776, 7054818944, 7063207808, 7071595136, 7079980928, 7088372608, 7096759424, 7105149824, 7113536896, 7121928064, 7130315392, 7138699648, 7147092352, 7155479168, 7163865728, 7172249984, 7180648064, 7189036672, 7197424768, 7205810816, 7214196608, 7222589824, 7230975104, 7239367552, 7247755904, 7256145536, 7264533376, 7272921472, 7281308032, 7289694848, 7298088832, 7306471808, 7314864512, 7323253888, 7331643008, 7340029568, 7348419712, 7356808832, 7365196672, 7373585792, 7381973888, 7390362752, 7398750592, 7407138944, 7415528576, 7423915648, 7432302208, 7440690304, 7449080192, 7457472128, 7465860992, 7474249088, 7482635648, 7491023744, 7499412608, 7507803008, 7516192384, 7524579968, 7532967296, 7541358464, 7549745792, 7558134656, 7566524032, 7574912896, 7583300992, 7591690112, 7600075136, 7608466816, 7616854912, 7625244544, 7633629824, 7642020992, 7650410368, 7658794112, 7667187328, 7675574912, 7683961984, 7692349568, 7700739712, 7709130368, 7717519232, 7725905536, 7734295424, 7742683264, 7751069056, 7759457408, 7767849088, 7776238208, 7784626816, 7793014912, 7801405312, 7809792128, 7818179968, 7826571136, 7834957184, 7843347328, 7851732352, 7860124544, 7868512384, 7876902016, 7885287808, 7893679744, 7902067072, 7910455936, 7918844288, 7927230848, 7935622784, 7944009344, 7952400256, 7960786048, 7969176704, 7977565312, 7985953408, 7994339968, 8002730368, 8011119488, 8019508096, 8027896192, 8036285056, 8044674688, 8053062272, 8061448832, 8069838464, 8078227328, 8086616704, 8095006592, 8103393664, 8111783552, 8120171392, 8128560256, 8136949376, 8145336704, 8153726848, 8162114944, 8170503296, 8178891904, 8187280768, 8195669632, 8204058496, 8212444544, 8220834176, 8229222272, 8237612672, 8246000768, 8254389376, 8262775168, 8271167104, 8279553664, 8287944064, 8296333184, 8304715136, 8313108352, 8321497984, 8329885568, 8338274432, 8346663296, 8355052928, 8363441536, 8371828352, 8380217984, 8388606592, 8396996224, 8405384576, 8413772672, 8422161536, 8430549376, 8438939008, 8447326592, 8455715456, 8464104832, 8472492928, 8480882048, 8489270656, 8497659776, 8506045312, 8514434944, 8522823808, 8531208832, 8539602304, 8547990656, 8556378752, 8564768384, 8573154176, 8581542784, 8589933952, 8598322816, 8606705024, 8615099264, 8623487872, 8631876992, 8640264064, 8648653952, 8657040256, 8665430656, 8673820544, 8682209152, 8690592128, 8698977152, 8707374464, 8715763328, 8724151424, 8732540032, 8740928384, 8749315712, 8757704576, 8766089344, 8774480768, 8782871936, 8791260032, 8799645824, 8808034432, 8816426368, 8824812928, 8833199488, 8841591424, 8849976448, 8858366336, 8866757248, 8875147136, 8883532928, 8891923328, 8900306816, 8908700288, 8917088384, 8925478784, 8933867392, 8942250368, 8950644608, 8959032704, 8967420544, 8975809664, 8984197504, 8992584064, 9000976256, 9009362048, 9017752448, 9026141312, 9034530688, 9042917504, 9051307904, 9059694208, 9068084864, 9076471424, 9084861824, 9093250688, 9101638528, 9110027648, 9118416512, 9126803584, 9135188096, 9143581312, 9151969664, 9160356224, 9168747136, 9177134464, 9185525632, 9193910144, 9202302848, 9210690688, 9219079552, 9227465344, 9235854464, 9244244864, 9252633472, 9261021824, 9269411456, 9277799296, 9286188928, 9294574208, 9302965888, 9311351936, 9319740032, 9328131968, 9336516736, 9344907392, 9353296768, 9361685888, 9370074752, 9378463616, 9386849408, 9395239808, 9403629184, 9412016512, 9420405376, 9428795008, 9437181568, 9445570688, 9453960832, 9462346624, 9470738048, 9479121536, 9487515008, 9495903616, 9504289664, 9512678528, 9521067904, 9529456256, 9537843584, 9546233728, 9554621312, 9563011456, 9571398784, 9579788672, 9588178304, 9596567168, 9604954496, 9613343104, 9621732992, 9630121856, 9638508416, 9646898816, 9655283584, 9663675776, 9672061312, 9680449664, 9688840064, 9697230464, 9705617536, 9714003584, 9722393984, 9730772608, 9739172224, 9747561088, 9755945344, 9764338816, 9772726144, 9781116544, 9789503872, 9797892992, 9806282624, 9814670464, 9823056512, 9831439232, 9839833984, 9848224384, 9856613504, 9865000576, 9873391232, 9881772416, 9890162816, 9898556288, 9906940544, 9915333248, 9923721088, 9932108672, 9940496512, 9948888448, 9957276544, 9965666176, 9974048384, 9982441088, 9990830464, 9999219584, 10007602816, 10015996544, 10024385152, 10032774016, 10041163648, 10049548928, 10057940096, 10066329472, 10074717824, 10083105152, 10091495296, 10099878784, 10108272256, 10116660608, 10125049216, 10133437312, 10141825664, 10150213504, 10158601088, 10166991232, 10175378816, 10183766144, 10192157312, 10200545408, 10208935552, 10217322112, 10225712768, 10234099328, 10242489472, 10250876032, 10259264896, 10267656064, 10276042624, 10284429184, 10292820352, 10301209472, 10309598848, 10317987712, 10326375296, 10334763392, 10343153536, 10351541632, 10359930752, 10368318592, 10376707456, 10385096576, 10393484672, 10401867136, 10410262144, 10418647424, 10427039104, 10435425664, 10443810176, 10452203648, 10460589952, 10468982144, 10477369472, 10485759104, 10494147712, 10502533504, 10510923392, 10519313536, 10527702656, 10536091264, 10544478592, 10552867712, 10561255808, 10569642368, 10578032768, 10586423168, 10594805632, 10603200128, 10611588992, 10619976064, 10628361344, 10636754048, 10645143424, 10653531776, 10661920384, 10670307968, 10678696832, 10687086464, 10695475072, 10703863168, 10712246144, 10720639616, 10729026688, 10737414784, 10745806208, 10754190976, 10762581376, 10770971264, 10779356288, 10787747456, 10796135552, 10804525184, 10812915584, 10821301888, 10829692288, 10838078336, 10846469248, 10854858368, 10863247232, 10871631488, 10880023424, 10888412032, 10896799616, 10905188992, 10913574016, 10921964672, 10930352768, 10938742912, 10947132544, 10955518592, 10963909504, 10972298368, 10980687488, 10989074816, 10997462912, 11005851776, 11014241152, 11022627712, 11031017344, 11039403904, 11047793024, 11056184704, 11064570752, 11072960896, 11081343872, 11089737856, 11098128256, 11106514816, 11114904448, 11123293568, 11131680128, 11140065152, 11148458368, 11156845696, 11165236864, 11173624192, 11182013824, 11190402688, 11198790784, 11207179136, 11215568768, 11223957376, 11232345728, 11240734592, 11249122688, 11257511296, 11265899648, 11274285952, 11282675584, 11291065472, 11299452544, 11307842432, 11316231296, 11324616832, 11333009024, 11341395584, 11349782656, 11358172288, 11366560384, 11374950016, 11383339648, 11391721856, 11400117376, 11408504192, 11416893568, 11425283456, 11433671552, 11442061184, 11450444672, 11458837888, 11467226752, 11475611776, 11484003968, 11492392064, 11500780672, 11509169024, 11517550976, 11525944448, 11534335616, 11542724224, 11551111808, 11559500672, 11567890304, 11576277376, 11584667008, 11593056128, 11601443456, 11609830016, 11618221952, 11626607488, 11634995072, 11643387776, 11651775104, 11660161664, 11668552576, 11676940928, 11685330304, 11693718656, 11702106496, 11710496128, 11718882688, 11727273088, 11735660416, 11744050048, 11752437376, 11760824704, 11769216128, 11777604736, 11785991296, 11794381952, 11802770048, 11811157888, 11819548544, 11827932544, 11836324736, 11844713344, 11853100928, 11861486464, 11869879936, 11878268032, 11886656896, 11895044992, 11903433088, 11911822976, 11920210816, 11928600448, 11936987264, 11945375872, 11953761152, 11962151296, 11970543488, 11978928512, 11987320448, 11995708288, 12004095104, 12012486272, 12020875136, 12029255552, 12037652096, 12046039168, 12054429568, 12062813824, 12071206528, 12079594624, 12087983744, 12096371072, 12104759936, 12113147264, 12121534592, 12129924992, 12138314624, 12146703232, 12155091584, 12163481216, 12171864704, 12180255872, 12188643968, 12197034112, 12205424512, 12213811328, 12222199424, 12230590336, 12238977664, 12247365248, 12255755392, 12264143488, 12272531584, 12280920448, 12289309568, 12297694592, 12306086528, 12314475392, 12322865024, 12331253632, 12339640448, 12348029312, 12356418944, 12364805248, 12373196672, 12381580928, 12389969024, 12398357632, 12406750592, 12415138432, 12423527552, 12431916416, 12440304512, 12448692352, 12457081216, 12465467776, 12473859968, 12482245504, 12490636672, 12499025536, 12507411584, 12515801728, 12524190592, 12532577152, 12540966272, 12549354368, 12557743232, 12566129536, 12574523264, 12582911872, 12591299456, 12599688064, 12608074624, 12616463488, 12624845696, 12633239936, 12641631616, 12650019968, 12658407296, 12666795136, 12675183232, 12683574656, 12691960192, 12700350592, 12708740224, 12717128576, 12725515904, 12733906816, 12742295168, 12750680192, 12759071872, 12767460736, 12775848832, 12784236928, 12792626816, 12801014656, 12809404288, 12817789312, 12826181504, 12834568832, 12842954624, 12851345792, 12859732352, 12868122496, 12876512128, 12884901248, 12893289088, 12901672832, 12910067584, 12918455168, 12926842496, 12935232896, 12943620736, 12952009856, 12960396928, 12968786816, 12977176192, 12985563776, 12993951104, 13002341504, 13010730368, 13019115392, 13027506304, 13035895168, 13044272512, 13052673152, 13061062528, 13069446272, 13077838976, 13086227072, 13094613632, 13103000192, 13111393664, 13119782528, 13128157568, 13136559232, 13144945024, 13153329536, 13161724288, 13170111872, 13178502784, 13186884736, 13195279744, 13203667072, 13212057472, 13220445824, 13228832128, 13237221248, 13245610624, 13254000512, 13262388352, 13270777472, 13279166336, 13287553408, 13295943296, 13304331904, 13312719488, 13321108096, 13329494656, 13337885824, 13346274944, 13354663808, 13363051136, 13371439232, 13379825024, 13388210816, 13396605056, 13404995456, 13413380224, 13421771392, 13430159744, 13438546048, 13446937216, 13455326848, 13463708288, 13472103808, 13480492672, 13488875648, 13497269888, 13505657728, 13514045312, 13522435712, 13530824576, 13539210112, 13547599232, 13555989376, 13564379008, 13572766336, 13581154432, 13589544832, 13597932928, 13606320512, 13614710656, 13623097472, 13631477632, 13639874944, 13648264064, 13656652928, 13665041792, 13673430656, 13681818496, 13690207616, 13698595712, 13706982272, 13715373184, 13723762048, 13732150144, 13740536704, 13748926592, 13757316224, 13765700992, 13774090112, 13782477952, 13790869376, 13799259008, 13807647872, 13816036736, 13824425344, 13832814208, 13841202304, 13849591424, 13857978752, 13866368896, 13874754688, 13883145344, 13891533184, 13899919232, 13908311168, 13916692096, 13925085056, 13933473152, 13941866368, 13950253696, 13958643584, 13967032192, 13975417216, 13983807616, 13992197504, 14000582272, 14008973696, 14017363072, 14025752192, 14034137984, 14042528384, 14050918016, 14059301504, 14067691648, 14076083584, 14084470144, 14092852352, 14101249664, 14109635968, 14118024832, 14126407552, 14134804352, 14143188608, 14151577984, 14159968384, 14168357248, 14176741504, 14185127296, 14193521024, 14201911424, 14210301824, 14218685056, 14227067264, 14235467392, 14243855488, 14252243072, 14260630144, 14269021568, 14277409408, 14285799296, 14294187904, 14302571392, 14310961792, 14319353728, 14327738752, 14336130944, 14344518784, 14352906368, 14361296512, 14369685376, 14378071424, 14386462592, 14394848128, 14403230848, 14411627392, 14420013952, 14428402304, 14436793472, 14445181568, 14453569664, 14461959808, 14470347904, 14478737024, 14487122816, 14495511424, 14503901824, 14512291712, 14520677504, 14529064832, 14537456768, 14545845632, 14554234496, 14562618496, 14571011456, 14579398784, 14587789184, 14596172672, 14604564608, 14612953984, 14621341312, 14629724288, 14638120832, 14646503296, 14654897536, 14663284864, 14671675264, 14680061056, 14688447616, 14696835968, 14705228416, 14713616768, 14722003328, 14730392192, 14738784128, 14747172736, 14755561088, 14763947648, 14772336512, 14780725376, 14789110144, 14797499776, 14805892736, 14814276992, 14822670208, 14831056256, 14839444352, 14847836032, 14856222848, 14864612992, 14872997504, 14881388672, 14889775744, 14898165376, 14906553472, 14914944896, 14923329664, 14931721856, 14940109696, 14948497024, 14956887424, 14965276544, 14973663616, 14982053248, 14990439808, 14998830976, 15007216768, 15015605888, 15023995264, 15032385152, 15040768384, 15049154944, 15057549184, 15065939072, 15074328448, 15082715008, 15091104128, 15099493504, 15107879296, 15116269184, 15124659584, 15133042304, 15141431936, 15149824384, 15158214272, 15166602368, 15174991232, 15183378304, 15191760512, 15200154496, 15208542592, 15216931712, 15225323392, 15233708416, 15242098048, 15250489216, 15258875264, 15267265408, 15275654528, 15284043136, 15292431488, 15300819584, 15309208192, 15317596544, 15325986176, 15334374784, 15342763648, 15351151744, 15359540608, 15367929728, 15376318336, 15384706432, 15393092992, 15401481856, 15409869952, 15418258816, 15426649984, 15435037568, 15443425664, 15451815296, 15460203392, 15468589184, 15476979328, 15485369216, 15493755776, 15502146944, 15510534272, 15518924416, 15527311232, 15535699072, 15544089472, 15552478336, 15560866688, 15569254528, 15577642624, 15586031488, 15594419072, 15602809472, 15611199104, 15619586432, 15627975296, 15636364928, 15644753792, 15653141888, 15661529216, 15669918848, 15678305152, 15686696576, 15695083136, 15703474048, 15711861632, 15720251264, 15728636288, 15737027456, 15745417088, 15753804928, 15762194048, 15770582656, 15778971008, 15787358336, 15795747712, 15804132224, 15812523392, 15820909696, 15829300096, 15837691264, 15846071936, 15854466944, 15862855808, 15871244672, 15879634816, 15888020608, 15896409728, 15904799104, 15913185152, 15921577088, 15929966464, 15938354816, 15946743424, 15955129472, 15963519872, 15971907968, 15980296064, 15988684928, 15997073024, 16005460864, 16013851264, 16022241152, 16030629248, 16039012736, 16047406976, 16055794816, 16064181376, 16072571264, 16080957824, 16089346688, 16097737856, 16106125184, 16114514816, 16122904192, 16131292544, 16139678848, 16148066944, 16156453504, 16164839552, 16173236096, 16181623424, 16190012032, 16198401152, 16206790528, 16215177344, 16223567744, 16231956352, 16240344704, 16248731008, 16257117824, 16265504384, 16273898624, 16282281856, 16290668672, 16299064192, 16307449216, 16315842176, 16324230016, 16332613504, 16341006464, 16349394304, 16357783168, 16366172288, 16374561664, 16382951296, 16391337856, 16399726208, 16408116352, 16416505472, 16424892032, 16433282176, 16441668224, 16450058624, 16458448768, 16466836864, 16475224448, 16483613056, 16492001408, 16500391808, 16508779648, 16517166976, 16525555328, 16533944192, 16542330752, 16550719616, 16559110528, 16567497088, 16575888512, 16584274816, 16592665472, 16601051008, 16609442944, 16617832064, 16626218624, 16634607488, 16642996096, 16651385728, 16659773824, 16668163712, 16676552576, 16684938112, 16693328768, 16701718144, 16710095488, 16718492288, 16726883968, 16735272832, 16743661184, 16752049792, 16760436608, 16768827008, 16777214336, 16785599104, 16793992832, 16802381696, 16810768768, 16819151744, 16827542656, 16835934848, 16844323712, 16852711552, 16861101952, 16869489536, 16877876864, 16886265728, 16894653056, 16903044736, 16911431296, 16919821696, 16928207488, 16936592768, 16944987776, 16953375616, 16961763968, 16970152832, 16978540928, 16986929536, 16995319168, 17003704448, 17012096896, 17020481152, 17028870784, 17037262208, 17045649536, 17054039936, 17062426496, 17070814336, 17079205504, 17087592064, 17095978112, 17104369024, 17112759424, 17121147776, 17129536384, 17137926016, 17146314368, 17154700928, 17163089792, 17171480192, 17179864192, 17188256896, 17196644992, 17205033856, 17213423488, 17221811072, 17230198912, 17238588032, 17246976896, 17255360384, 17263754624, 17272143232, 17280530048, 17288918912, 17297309312, 17305696384, 17314085504, 17322475136, 17330863744, 17339252096, 17347640192, 17356026496, 17364413824, 17372796544, 17381190016, 17389583488, 17397972608, 17406360704, 17414748544, 17423135872, 17431527296, 17439915904, 17448303232, 17456691584, 17465081728, 17473468288, 17481857408, 17490247552, 17498635904, 17507022464, 17515409024, 17523801728, 17532189824, 17540577664, 17548966016, 17557353344, 17565741184, 17574131584, 17582519168, 17590907008, 17599296128, 17607687808, 17616076672, 17624455808, 17632852352, 17641238656, 17649630848, 17658018944, 17666403968, 17674794112, 17683178368, 17691573376, 17699962496, 17708350592, 17716739968, 17725126528, 17733517184, 17741898112, 17750293888, 17758673024, 17767070336, 17775458432, 17783848832, 17792236928, 17800625536, 17809012352, 17817402752, 17825785984, 17834178944, 17842563968, 17850955648, 17859344512, 17867732864, 17876119424, 17884511872, 17892900224, 17901287296, 17909677696, 17918058112, 17926451072, 17934843776, 17943230848, 17951609216, 17960008576, 17968397696, 17976784256, 17985175424, 17993564032, 18001952128, 18010339712, 18018728576, 18027116672, 18035503232, 18043894144, 18052283264, 18060672128, 18069056384, 18077449856, 18085837184, 18094225792, 18102613376, 18111004544, 18119388544, 18127781248, 18136170368, 18144558976, 18152947328, 18161336192, 18169724288, 18178108544, 18186498944, 18194886784, 18203275648, 18211666048, 18220048768, 18228444544, 18236833408, 18245220736] cache_sizes = [ 16776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072, 17693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088, 18611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208, 19529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968, 20446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216, 21364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104, 22281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096, 23198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112, 24116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488, 25034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096, 25951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472, 26869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744, 27786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504, 28700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752, 29621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976, 30538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248, 31456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392, 32372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768, 33289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992, 34208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984, 35127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976, 36044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656, 36961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904, 37879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672, 38795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632, 39713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032, 40631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304, 41547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912, 42467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696, 43382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432, 44302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448, 45219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208, 46136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328, 47053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936, 47971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312, 48889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712, 49807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472, 50724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848, 51641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968, 52557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576, 53475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744, 54394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248, 55312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856, 56228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488, 57146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632, 58064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984, 58981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512, 59897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968, 60817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752, 61733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512, 62651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656, 63569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392, 64486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792, 65402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296, 66321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672, 67239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304, 68157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912, 69074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184, 69989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816, 70907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168, 71826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568, 72744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944, 73662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832, 74579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544, 75497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072, 76414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832, 77331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336, 78249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664, 79166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472, 80084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848, 81002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304, 81919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984, 82835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464, 83753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608, 84672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496, 85589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112, 86506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632, 87424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264, 88341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384, 89259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376, 90177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776, 91093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384, 92012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912, 92926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136, 93845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896, 94764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016, 95681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544, 96599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536, 97517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168, 98434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928, 99352384, 99482816, 99614272, 99745472, 99876416, 100007104, 100138048, 100267072, 100401088, 100529984, 100662592, 100791872, 100925248, 101056064, 101187392, 101317952, 101449408, 101580608, 101711296, 101841728, 101973824, 102104896, 102235712, 102366016, 102498112, 102628672, 102760384, 102890432, 103021888, 103153472, 103284032, 103415744, 103545152, 103677248, 103808576, 103939648, 104070976, 104201792, 104332736, 104462528, 104594752, 104725952, 104854592, 104988608, 105118912, 105247808, 105381184, 105511232, 105643072, 105774784, 105903296, 106037056, 106167872, 106298944, 106429504, 106561472, 106691392, 106822592, 106954304, 107085376, 107216576, 107346368, 107478464, 107609792, 107739712, 107872192, 108003136, 108131392, 108265408, 108396224, 108527168, 108657344, 108789568, 108920384, 109049792, 109182272, 109312576, 109444928, 109572928, 109706944, 109837888, 109969088, 110099648, 110230976, 110362432, 110492992, 110624704, 110755264, 110886208, 111017408, 111148864, 111279296, 111410752, 111541952, 111673024, 111803456, 111933632, 112066496, 112196416, 112328512, 112457792, 112590784, 112715968, 112852672, 112983616, 113114944, 113244224, 113376448, 113505472, 113639104, 113770304, 113901376, 114031552, 114163264, 114294592, 114425536, 114556864, 114687424, 114818624, 114948544, 115080512, 115212224, 115343296, 115473472, 115605184, 115736128, 115867072, 115997248, 116128576, 116260288, 116391488, 116522944, 116652992, 116784704, 116915648, 117046208, 117178304, 117308608, 117440192, 117569728, 117701824, 117833024, 117964096, 118094656, 118225984, 118357312, 118489024, 118617536, 118749632, 118882112, 119012416, 119144384, 119275328, 119406016, 119537344, 119668672, 119798464, 119928896, 120061376, 120192832, 120321728, 120454336, 120584512, 120716608, 120848192, 120979136, 121109056, 121241408, 121372352, 121502912, 121634752, 121764416, 121895744, 122027072, 122157632, 122289088, 122421184, 122550592, 122682944, 122813888, 122945344, 123075776, 123207488, 123338048, 123468736, 123600704, 123731264, 123861952, 123993664, 124124608, 124256192, 124386368, 124518208, 124649024, 124778048, 124911296, 125041088, 125173696, 125303744, 125432896, 125566912, 125696576, 125829056, 125958592, 126090304, 126221248, 126352832, 126483776, 126615232, 126746432, 126876608, 127008704, 127139392, 127270336, 127401152, 127532224, 127663552, 127794752, 127925696, 128055232, 128188096, 128319424, 128449856, 128581312, 128712256, 128843584, 128973632, 129103808, 129236288, 129365696, 129498944, 129629888, 129760832, 129892288, 130023104, 130154048, 130283968, 130416448, 130547008, 130678336, 130807616, 130939456, 131071552, 131202112, 131331776, 131464384, 131594048, 131727296, 131858368, 131987392, 132120256, 132250816, 132382528, 132513728, 132644672, 132774976, 132905792, 133038016, 133168832, 133299392, 133429312, 133562048, 133692992, 133823296, 133954624, 134086336, 134217152, 134348608, 134479808, 134607296, 134741056, 134872384, 135002944, 135134144, 135265472, 135396544, 135527872, 135659072, 135787712, 135921472, 136052416, 136182848, 136313792, 136444864, 136576448, 136707904, 136837952, 136970048, 137099584, 137232064, 137363392, 137494208, 137625536, 137755712, 137887424, 138018368, 138149824, 138280256, 138411584, 138539584, 138672832, 138804928, 138936128, 139066688, 139196864, 139328704, 139460032, 139590208, 139721024, 139852864, 139984576, 140115776, 140245696, 140376512, 140508352, 140640064, 140769856, 140902336, 141032768, 141162688, 141294016, 141426496, 141556544, 141687488, 141819584, 141949888, 142080448, 142212544, 142342336, 142474432, 142606144, 142736192, 142868288, 142997824, 143129408, 143258944, 143392448, 143523136, 143653696, 143785024, 143916992, 144045632, 144177856, 144309184, 144440768, 144570688, 144701888, 144832448, 144965056, 145096384, 145227584, 145358656, 145489856, 145620928, 145751488, 145883072, 146011456, 146144704, 146275264, 146407232, 146538176, 146668736, 146800448, 146931392, 147062336, 147193664, 147324224, 147455936, 147586624, 147717056, 147848768, 147979456, 148110784, 148242368, 148373312, 148503232, 148635584, 148766144, 148897088, 149028416, 149159488, 149290688, 149420224, 149551552, 149683136, 149814976, 149943616, 150076352, 150208064, 150338624, 150470464, 150600256, 150732224, 150862784, 150993088, 151125952, 151254976, 151388096, 151519168, 151649728, 151778752, 151911104, 152042944, 152174144, 152304704, 152435648, 152567488, 152698816, 152828992, 152960576, 153091648, 153222976, 153353792, 153484096, 153616192, 153747008, 153878336, 154008256, 154139968, 154270912, 154402624, 154533824, 154663616, 154795712, 154926272, 155057984, 155188928, 155319872, 155450816, 155580608, 155712064, 155843392, 155971136, 156106688, 156237376, 156367424, 156499264, 156630976, 156761536, 156892352, 157024064, 157155008, 157284416, 157415872, 157545536, 157677248, 157810496, 157938112, 158071744, 158203328, 158334656, 158464832, 158596288, 158727616, 158858048, 158988992, 159121216, 159252416, 159381568, 159513152, 159645632, 159776192, 159906496, 160038464, 160169536, 160300352, 160430656, 160563008, 160693952, 160822208, 160956352, 161086784, 161217344, 161349184, 161480512, 161611456, 161742272, 161873216, 162002752, 162135872, 162266432, 162397888, 162529216, 162660032, 162790976, 162922048, 163052096, 163184576, 163314752, 163446592, 163577408, 163707968, 163839296, 163969984, 164100928, 164233024, 164364224, 164494912, 164625856, 164756672, 164887616, 165019072, 165150016, 165280064, 165412672, 165543104, 165674944, 165805888, 165936832, 166067648, 166198336, 166330048, 166461248, 166591552, 166722496, 166854208, 166985408, 167116736, 167246656, 167378368, 167508416, 167641024, 167771584, 167903168, 168034112, 168164032, 168295744, 168427456, 168557632, 168688448, 168819136, 168951616, 169082176, 169213504, 169344832, 169475648, 169605952, 169738048, 169866304, 169999552, 170131264, 170262464, 170393536, 170524352, 170655424, 170782016, 170917696, 171048896, 171179072, 171310784, 171439936, 171573184, 171702976, 171835072, 171966272, 172097216, 172228288, 172359232, 172489664, 172621376, 172747712, 172883264, 173014208, 173144512, 173275072, 173407424, 173539136, 173669696, 173800768, 173931712, 174063424, 174193472, 174325696, 174455744, 174586816, 174718912, 174849728, 174977728, 175109696, 175242688, 175374272, 175504832, 175636288, 175765696, 175898432, 176028992, 176159936, 176291264, 176422592, 176552512, 176684864, 176815424, 176946496, 177076544, 177209152, 177340096, 177470528, 177600704, 177731648, 177864256, 177994816, 178126528, 178257472, 178387648, 178518464, 178650176, 178781888, 178912064, 179044288, 179174848, 179305024, 179436736, 179568448, 179698496, 179830208, 179960512, 180092608, 180223808, 180354752, 180485696, 180617152, 180748096, 180877504, 181009984, 181139264, 181272512, 181402688, 181532608, 181663168, 181795136, 181926592, 182057536, 182190016, 182320192, 182451904, 182582336, 182713792, 182843072, 182976064, 183107264, 183237056, 183368384, 183494848, 183631424, 183762752, 183893824, 184024768, 184154816, 184286656, 184417984, 184548928, 184680128, 184810816, 184941248, 185072704, 185203904, 185335616, 185465408, 185596352, 185727296, 185859904, 185989696, 186121664, 186252992, 186383552, 186514112, 186645952, 186777152, 186907328, 187037504, 187170112, 187301824, 187429184, 187562048, 187693504, 187825472, 187957184, 188087104, 188218304, 188349376, 188481344, 188609728, 188743616, 188874304, 189005248, 189136448, 189265088, 189396544, 189528128, 189660992, 189791936, 189923264, 190054208, 190182848, 190315072, 190447424, 190577984, 190709312, 190840768, 190971328, 191102656, 191233472, 191364032, 191495872, 191626816, 191758016, 191888192, 192020288, 192148928, 192282176, 192413504, 192542528, 192674752, 192805952, 192937792, 193068608, 193198912, 193330496, 193462208, 193592384, 193723456, 193854272, 193985984, 194116672, 194247232, 194379712, 194508352, 194641856, 194772544, 194900672, 195035072, 195166016, 195296704, 195428032, 195558592, 195690304, 195818176, 195952576, 196083392, 196214336, 196345792, 196476736, 196607552, 196739008, 196869952, 197000768, 197130688, 197262784, 197394368, 197523904, 197656384, 197787584, 197916608, 198049472, 198180544, 198310208, 198442432, 198573632, 198705088, 198834368, 198967232, 199097792, 199228352, 199360192, 199491392, 199621696, 199751744, 199883968, 200014016, 200146624, 200276672, 200408128, 200540096, 200671168, 200801984, 200933312, 201062464, 201194944, 201326144, 201457472, 201588544, 201719744, 201850816, 201981632, 202111552, 202244032, 202374464, 202505152, 202636352, 202767808, 202898368, 203030336, 203159872, 203292608, 203423296, 203553472, 203685824, 203816896, 203947712, 204078272, 204208192, 204341056, 204472256, 204603328, 204733888, 204864448, 204996544, 205125568, 205258304, 205388864, 205517632, 205650112, 205782208, 205913536, 206044736, 206176192, 206307008, 206434496, 206569024, 206700224, 206831168, 206961856, 207093056, 207223616, 207355328, 207486784, 207616832, 207749056, 207879104, 208010048, 208141888, 208273216, 208404032, 208534336, 208666048, 208796864, 208927424, 209059264, 209189824, 209321792, 209451584, 209582656, 209715136, 209845568, 209976896, 210106432, 210239296, 210370112, 210501568, 210630976, 210763712, 210894272, 211024832, 211156672, 211287616, 211418176, 211549376, 211679296, 211812032, 211942592, 212074432, 212204864, 212334016, 212467648, 212597824, 212727616, 212860352, 212991424, 213120832, 213253952, 213385024, 213515584, 213645632, 213777728, 213909184, 214040128, 214170688, 214302656, 214433728, 214564544, 214695232, 214826048, 214956992, 215089088, 215219776, 215350592, 215482304, 215613248, 215743552, 215874752, 216005312, 216137024, 216267328, 216399296, 216530752, 216661696, 216790592, 216923968, 217054528, 217183168, 217316672, 217448128, 217579072, 217709504, 217838912, 217972672, 218102848, 218233024, 218364736, 218496832, 218627776, 218759104, 218888896, 219021248, 219151936, 219281728, 219413056, 219545024, 219675968, 219807296, 219938624, 220069312, 220200128, 220331456, 220461632, 220592704, 220725184, 220855744, 220987072, 221117888, 221249216, 221378368, 221510336, 221642048, 221772736, 221904832, 222031808, 222166976, 222297536, 222428992, 222559936, 222690368, 222820672, 222953152, 223083968, 223213376, 223345984, 223476928, 223608512, 223738688, 223869376, 224001472, 224132672, 224262848, 224394944, 224524864, 224657344, 224788288, 224919488, 225050432, 225181504, 225312704, 225443776, 225574592, 225704768, 225834176, 225966784, 226097216, 226229824, 226360384, 226491712, 226623424, 226754368, 226885312, 227015104, 227147456, 227278528, 227409472, 227539904, 227669696, 227802944, 227932352, 228065216, 228196288, 228326464, 228457792, 228588736, 228720064, 228850112, 228981056, 229113152, 229243328, 229375936, 229505344, 229636928, 229769152, 229894976, 230030272, 230162368, 230292416, 230424512, 230553152, 230684864, 230816704, 230948416, 231079616, 231210944, 231342016, 231472448, 231603776, 231733952, 231866176, 231996736, 232127296, 232259392, 232388672, 232521664, 232652608, 232782272, 232914496, 233043904, 233175616, 233306816, 233438528, 233569984, 233699776, 233830592, 233962688, 234092224, 234221888, 234353984, 234485312, 234618304, 234749888, 234880832, 235011776, 235142464, 235274048, 235403456, 235535936, 235667392, 235797568, 235928768, 236057152, 236190272, 236322752, 236453312, 236583616, 236715712, 236846528, 236976448, 237108544, 237239104, 237371072, 237501632, 237630784, 237764416, 237895232, 238026688, 238157632, 238286912, 238419392, 238548032, 238681024, 238812608, 238941632, 239075008, 239206336, 239335232, 239466944, 239599168, 239730496, 239861312, 239992384, 240122816, 240254656, 240385856, 240516928, 240647872, 240779072, 240909632, 241040704, 241171904, 241302848, 241433408, 241565248, 241696192, 241825984, 241958848, 242088256, 242220224, 242352064, 242481856, 242611648, 242744896, 242876224, 243005632, 243138496, 243268672, 243400384, 243531712, 243662656, 243793856, 243924544, 244054592, 244187072, 244316608, 244448704, 244580032, 244710976, 244841536, 244972864, 245104448, 245233984, 245365312, 245497792, 245628736, 245759936, 245889856, 246021056, 246152512, 246284224, 246415168, 246545344, 246675904, 246808384, 246939584, 247070144, 247199552, 247331648, 247463872, 247593536, 247726016, 247857088, 247987648, 248116928, 248249536, 248380736, 248512064, 248643008, 248773312, 248901056, 249036608, 249167552, 249298624, 249429184, 249560512, 249692096, 249822784, 249954112, 250085312, 250215488, 250345792, 250478528, 250608704, 250739264, 250870976, 251002816, 251133632, 251263552, 251395136, 251523904, 251657792, 251789248, 251919424, 252051392, 252182464, 252313408, 252444224, 252575552, 252706624, 252836032, 252968512, 253099712, 253227584, 253361728, 253493056, 253623488, 253754432, 253885504, 254017216, 254148032, 254279488, 254410432, 254541376, 254672576, 254803264, 254933824, 255065792, 255196736, 255326528, 255458752, 255589952, 255721408, 255851072, 255983296, 256114624, 256244416, 256374208, 256507712, 256636096, 256768832, 256900544, 257031616, 257162176, 257294272, 257424448, 257555776, 257686976, 257818432, 257949632, 258079552, 258211136, 258342464, 258473408, 258603712, 258734656, 258867008, 258996544, 259127744, 259260224, 259391296, 259522112, 259651904, 259784384, 259915328, 260045888, 260175424, 260308544, 260438336, 260570944, 260700992, 260832448, 260963776, 261092672, 261226304, 261356864, 261487936, 261619648, 261750592, 261879872, 262011968, 262143424, 262274752, 262404416, 262537024, 262667968, 262799296, 262928704, 263061184, 263191744, 263322944, 263454656, 263585216, 263716672, 263847872, 263978944, 264108608, 264241088, 264371648, 264501184, 264632768, 264764096, 264895936, 265024576, 265158464, 265287488, 265418432, 265550528, 265681216, 265813312, 265943488, 266075968, 266206144, 266337728, 266468032, 266600384, 266731072, 266862272, 266993344, 267124288, 267255616, 267386432, 267516992, 267648704, 267777728, 267910592, 268040512, 268172096, 268302784, 268435264, 268566208, 268696256, 268828096, 268959296, 269090368, 269221312, 269352256, 269482688, 269614784, 269745856, 269876416, 270007616, 270139328, 270270272, 270401216, 270531904, 270663616, 270791744, 270924736, 271056832, 271186112, 271317184, 271449536, 271580992, 271711936, 271843136, 271973056, 272105408, 272236352, 272367296, 272498368, 272629568, 272759488, 272891456, 273022784, 273153856, 273284672, 273415616, 273547072, 273677632, 273808448, 273937088, 274071488, 274200896, 274332992, 274463296, 274595392, 274726208, 274857536, 274988992, 275118656, 275250496, 275382208, 275513024, 275643968, 275775296, 275906368, 276037184, 276167872, 276297664, 276429376, 276560576, 276692672, 276822976, 276955072, 277085632, 277216832, 277347008, 277478848, 277609664, 277740992, 277868608, 278002624, 278134336, 278265536, 278395328, 278526784, 278657728, 278789824, 278921152, 279052096, 279182912, 279313088, 279443776, 279576256, 279706048, 279838528, 279969728, 280099648, 280230976, 280361408, 280493632, 280622528, 280755392, 280887104, 281018176, 281147968, 281278912, 281411392, 281542592, 281673152, 281803712, 281935552, 282066496, 282197312, 282329024, 282458816, 282590272, 282720832, 282853184, 282983744, 283115072, 283246144, 283377344, 283508416, 283639744, 283770304, 283901504, 284032576, 284163136, 284294848, 284426176, 284556992, 284687296, 284819264, 284950208, 285081536] ```