Ethash

Ethash era l'algoritmo di mining di proof-of-work di Ethereum. Il proof-of-work è ora stato **disattivato interamente** e, invece, Ethereum è ora protetto utilizzando il proof-of-stake. Leggi di più su La Fusione, sul proof-of-stake e sullo staking. Questa pagina è per interesse storico!

Ethash(opens in a new tab) è una versione modificata dell'algoritmo di Dagger-Hashimoto. Il proof-of-work di Ethash è a elevato consumo di memoria(opens in a new tab), cosa pensata per rendere l'algoritmo resistente agli ASIC. Gli ASIC di Ethash sono infine stati sviluppati, ma il mining della GPU è stata un'opzione ancora valida fino alla disattivazione del proof-of-work. Ethash è ancora usato per minare altre valute su altre reti di proof-of-work non di Ethereum.

Come funziona Ethash?

La gravosità sulla memoria è ottenuta con un algoritmo di proof-of-work che richiede la scelta di sotto-serie di una risorsa fissa, dipendente dal nonce e dall'intestazione del blocco. Questa risorsa (di pochi gigabyte di dimensioni) è detta DAG. Il DAG è modificato ogni 30.000 blocchi, una finestra di circa 125 ore detta un'epoca (circa 5,2 giorni) e richiede un po' di tempo per generarsi. Poiché il DAG dipende solo dall'altezza del blocco, può esser pre-generato, ma se non è il client, deve attendere fino alla fine di questo processo per produrre un blocco. Se i client non si pre-generano e salvano anticipatamente nella cache i DAG, la rete potrebbe subire un enorme ritardo dei blocchi a ogni transizione d'epoca. Il DAG non deve necessariamente essere generato per verificare il proof-of-work, perché è essenzialmente possibile eseguire la verifica con poca CPU e poca memoria.

Il percorso generale intrapreso dall'algoritmo è il seguente:

Esiste un seed, calcolabile per ogni blocco scansionando fino a quel punto le intestazioni dei blocchi.
Dal seed, si può calcolare una cache pseudo-casuale di 16 MB. I client leggeri memorizzano la cache.
Dalla cache, possiamo generare un dataset di 1 GB, caratterizzato dal fatto che ogni elemento nel dataset dipende solo da una piccola quantità di elementi dalla cache. I client completi e i miner memorizzano il dataset. Il dataset cresce linearmente col tempo.
Durante il mining vengono prese delle fette (slice) casuali del dataset, eseguendone l'hashing. La verifica può essere effettuata con poca memoria usando la cache per rigenerare le parti specifiche del dataset necessarie, così da dover solo memorizzare la cache.

Il grande dataset è aggiornato una volta ogni 30.000 blocchi, in questo modo l'impegno di un miner sarà per lo più quello di leggere il dataset, non effettuare modifiche a esso.

Definizioni

Adottiamo le seguenti definizioni:

1WORD_BYTES = 4                    # bytes in word
2DATASET_BYTES_INIT = 2**30        # bytes in dataset at genesis
3DATASET_BYTES_GROWTH = 2**23      # dataset growth per epoch
4CACHE_BYTES_INIT = 2**24          # bytes in cache at genesis
5CACHE_BYTES_GROWTH = 2**17        # cache growth per epoch
6CACHE_MULTIPLIER=1024             # Size of the DAG relative to the cache
7EPOCH_LENGTH = 30000              # blocks per epoch
8MIX_BYTES = 128                   # width of mix
9HASH_BYTES = 64                   # hash length in bytes
10DATASET_PARENTS = 256             # number of parents of each dataset element
11CACHE_ROUNDS = 3                  # number of rounds in cache production
12ACCESSES = 64                     # number of accesses in hashimoto loop
Mostra tutto

L'uso di "SHA3"

Lo sviluppo di Ethereum è coinciso con lo sviluppo dello standard SHA3 e il processo standard ha effettuato una modifica tardiva al padding dell'algoritmo di hash finalizzato, quindi, gli hash "sha3_256" e "sha3_512" di Ethereum non sono hash dello standard sha3, ma una variante, spesso definita "Keccak-256" e "Keccak-512" in altri contesti. Vedi la discussione, ad esempio qui(opens in a new tab), qui(opens in a new tab) o qui(opens in a new tab).

Si ricorda che gli hash "sha3" siano presentati nella descrizione dell'algoritmo più avanti.

Parametri

I parametri della cache e del dataset di Ethash dipendono dal numero del blocco. Le dimensioni della cache e del dataset crescono entrambe linearmente; tuttavia, prendiamo sempre il numero primo maggiore successivo alla soglia di crescita lineare, per ridurre il rischio di regolarità accidentali che determinano un comportamento ciclico.

1def get_cache_size(block_number):
2    sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
3    sz -= HASH_BYTES
4    while not isprime(sz / HASH_BYTES):
5        sz -= 2 * HASH_BYTES
6    return sz
7
8def get_full_size(block_number):
9    sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
10    sz -= MIX_BYTES
11    while not isprime(sz / MIX_BYTES):
12        sz -= 2 * MIX_BYTES
13    return sz
Mostra tutto
 Copia

Nell'appendice sono presentate tabelle delle dimensioni del dataset e della cache.

Generazione della cache

Specifichiamo ora la funzione per produrre una cache:

1def mkcache(cache_size, seed):
2    n = cache_size // HASH_BYTES
3
4    # Sequentially produce the initial dataset
5    o = [sha3_512(seed)]
6    for i in range(1, n):
7        o.append(sha3_512(o[-1]))
8
9    # Use a low-round version of randmemohash
10    for _ in range(CACHE_ROUNDS):
11        for i in range(n):
12            v = o[i][0] % n
13            o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))
14
15    return o
Mostra tutto
 Copia

Il processo di produzione della cache richiede dapprima il riempimento sequenziale di 32 MB di memoria, poi l'esecuzione di due passaggi dell'algoritmo RandMemoHash di Sergio Demian Lerner da Strict Memory Hard Hashing Functions (2014)(opens in a new tab). L'output è una serie di valori a 64 byte 524288.

Funzione di aggregazione dei dati

Usiamo un algoritmo ispirato dall'hash FNV(opens in a new tab) in alcuni casi come un sostituto non associativo per XOR. Nota che moltiplichiamo il numero primo con l'intero input a 32 bit, a differenza della specifica FNV-1, che moltiplica invece il numero primo con un byte (ottetto).

1FNV_PRIME = 0x01000193
2
3def fnv(v1, v2):
4    return ((v1 * FNV_PRIME) ^ v2) % 2**32
 Copia

Anche lo yellow paper specifica fnv come v1*(FNV_PRIME ^ v2), tutte le implementazioni correnti usano attualmente la suddetta definizione.

Calcolo dell'intero dataset

Ogni elemento da 64 byte nell'intero dataset da 1 GB è calcolato come segue:

1def calc_dataset_item(cache, i):
2    n = len(cache)
3    r = HASH_BYTES // WORD_BYTES
4    # initialize the mix
5    mix = copy.copy(cache[i % n])
6    mix[0] ^= i
7    mix = sha3_512(mix)
8    # fnv it with a lot of random cache nodes based on i
9    for j in range(DATASET_PARENTS):
10        cache_index = fnv(i ^ j, mix[j % r])
11        mix = map(fnv, mix, cache[cache_index % n])
12    return sha3_512(mix)
Mostra tutto
 Copia

Essenzialmente, combiniamo i dati da 256 nodi della cache selezionati pseudo-casualmente e ne eseguiamo l'hash per calcolare il nodo del dataset. L'intero dataset è quindi generato da:

1def calc_dataset(full_size, cache):
2    return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]
 Copia

Ciclo principale

Ora, specifichiamo il ciclo principale in stile "hashimoto", dove aggreghiamo i dati dal dataset completo per poter produrre il valore finale per un'intestazione e nonce in particolare. Nel codice seguente, header rappresenta l'hash SHA3-256 della rappresentazione RLP di un'intestazione del blocco troncata, ovvero, di un'intestazione che esclude i campi mixHash e nonce. Un nonce si compone degli otto byte di un intero non firmato da 64 bit, con ordinamento big-endian. Quindi nonce[::-1] è la rappresentazione little-endian di otto byte di quel valore:

1def hashimoto(header, nonce, full_size, dataset_lookup):
2    n = full_size / HASH_BYTES
3    w = MIX_BYTES // WORD_BYTES
4    mixhashes = MIX_BYTES / HASH_BYTES
5    # combine header+nonce into a 64 byte seed
6    s = sha3_512(header + nonce[::-1])
7    # start the mix with replicated s
8    mix = []
9    for _ in range(MIX_BYTES / HASH_BYTES):
10        mix.extend(s)
11    # mix in random dataset nodes
12    for i in range(ACCESSES):
13        p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
14        newdata = []
15        for j in range(MIX_BYTES / HASH_BYTES):
16            newdata.extend(dataset_lookup(p + j))
17        mix = map(fnv, mix, newdata)
18    # compress mix
19    cmix = []
20    for i in range(0, len(mix), 4):
21        cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))
22    return {
23        "mix digest": serialize_hash(cmix),
24        "result": serialize_hash(sha3_256(s+cmix))
25    }
26
27def hashimoto_light(full_size, cache, header, nonce):
28    return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))
29
30def hashimoto_full(full_size, dataset, header, nonce):
31    return hashimoto(header, nonce, full_size, lambda x: dataset[x])
Mostra tutto
 Copia

Essenzialmente, manteniamo un mix di 128 byte e recuperiamo sequenzialmente e ripetutamente 128 byte dal dataset completo e usiamo la funzione fnv per combinarli col mix. Vengono usati 128 byte di accesso sequenziale così che ogni ciclo dell'algoritmo recuperi sempre una pagina intera dalla RAM, minimizzando le ricerche a vuoto nel lookaside buffer che gli ASIC dovrebbero teoricamente poter evitare.

Se l'output di questo algoritmo è inferiore all'obiettivo desiderato, allora il nonce è valido. Nota che l'applicazione aggiuntiva di sha3_256 alla fine assicura che esista un nonce intermedio, che può essere fornito per provare che almeno una piccola quantità di lavoro è stata eseguita; questa rapida verifica di PoW esterna è utilizzabile per scopi anti-DDoS. Serve anche a fornire la garanzia statistica che il risultato sia un numero a 256 bit imparziale.

Mining

L'algoritmo di mining è definito come segue:

1def mine(full_size, dataset, header, difficulty):
2    # zero-pad target to compare with hash on the same digit
3    target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
4    from random import randint
5    nonce = randint(0, 2**64)
6    while hashimoto_full(full_size, dataset, header, nonce) > target:
7        nonce = (nonce + 1) % 2**64
8    return nonce
 Copia

Definire l'hash del seed

Per poter calcolare l'hash del seed da usare per fare mining su un dato blocco, usiamo il seguente algoritmo:

1 def get_seedhash(block):
2     s = '\x00' * 32
3     for i in range(block.number // EPOCH_LENGTH):
4         s = serialize_hash(sha3_256(s))
5     return s
 Copia

Nota che per la fluidità delle attività di mining e verifica, consigliamo di pre-calcolare gli hash dei seed futuri e i dataset in un thread separato.

Letture consigliate

Conosci una risorsa della community che ti è stata utile? Modifica questa pagina e aggiungila!

Appendice

Il seguente codice dovrebbe essere anteposto se sei interessato all'esecuzione della suddetta specifica di Python come codice.

1import sha3, copy
2
3# Assumes little endian bit ordering (same as Intel architectures)
4def decode_int(s):
5    return int(s[::-1].encode('hex'), 16) if s else 0
6
7def encode_int(s):
8    a = "%x" % s
9    return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]
10
11def zpad(s, length):
12    return s + '\x00' * max(0, length - len(s))
13
14def serialize_hash(h):
15    return ''.join([zpad(encode_int(x), 4) for x in h])
16
17def deserialize_hash(h):
18    return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
19
20def hash_words(h, sz, x):
21    if isinstance(x, list):
22        x = serialize_hash(x)
23    y = h(x)
24    return deserialize_hash(y)
25
26def serialize_cache(ds):
27    return ''.join([serialize_hash(h) for h in ds])
28
29serialize_dataset = serialize_cache
30
31# sha3 hash function, outputs 64 bytes
32def sha3_512(x):
33    return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)
34
35def sha3_256(x):
36    return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)
37
38def xor(a, b):
39    return a ^ b
40
41def isprime(x):
42    for i in range(2, int(x**0.5)):
43         if x % i == 0:
44             return False
45    return True
Mostra tutto
 Copia

Dimensioni dei dati

Le seguenti tabelle di ricerca forniscono approssimativamente 2048 epoche tabulate di dimensioni dei dati e della cache.

1def get_datasize(block_number):
2    return data_sizes[block_number // EPOCH_LENGTH]
3
4def get_cachesize(block_number):
5    return cache_sizes[block_number // EPOCH_LENGTH]
6
7data_sizes = [
81073739904, 1082130304, 1090514816, 1098906752, 1107293056,
91115684224, 1124070016, 1132461952, 1140849536, 1149232768,
101157627776, 1166013824, 1174404736, 1182786944, 1191180416,
111199568512, 1207958912, 1216345216, 1224732032, 1233124736,
121241513344, 1249902464, 1258290304, 1266673792, 1275067264,
131283453312, 1291844992, 1300234112, 1308619904, 1317010048,
141325397376, 1333787776, 1342176128, 1350561664, 1358954368,
151367339392, 1375731584, 1384118144, 1392507008, 1400897408,
161409284736, 1417673344, 1426062464, 1434451072, 1442839168,
171451229056, 1459615616, 1468006016, 1476394112, 1484782976,
181493171584, 1501559168, 1509948032, 1518337664, 1526726528,
191535114624, 1543503488, 1551892096, 1560278656, 1568669056,
201577056384, 1585446272, 1593831296, 1602219392, 1610610304,
211619000192, 1627386752, 1635773824, 1644164224, 1652555648,
221660943488, 1669332608, 1677721216, 1686109312, 1694497664,
231702886272, 1711274624, 1719661184, 1728047744, 1736434816,
241744829056, 1753218944, 1761606272, 1769995904, 1778382464,
251786772864, 1795157888, 1803550592, 1811937664, 1820327552,
261828711552, 1837102976, 1845488768, 1853879936, 1862269312,
271870656896, 1879048064, 1887431552, 1895825024, 1904212096,
281912601216, 1920988544, 1929379456, 1937765504, 1946156672,
291954543232, 1962932096, 1971321728, 1979707264, 1988093056,
301996487552, 2004874624, 2013262208, 2021653888, 2030039936,
312038430848, 2046819968, 2055208576, 2063596672, 2071981952,
322080373632, 2088762752, 2097149056, 2105539712, 2113928576,
332122315136, 2130700672, 2139092608, 2147483264, 2155872128,
342164257664, 2172642176, 2181035392, 2189426048, 2197814912,
352206203008, 2214587264, 2222979712, 2231367808, 2239758208,
362248145024, 2256527744, 2264922752, 2273312128, 2281701248,
372290086272, 2298476672, 2306867072, 2315251072, 2323639168,
382332032128, 2340420224, 2348808064, 2357196416, 2365580416,
392373966976, 2382363008, 2390748544, 2399139968, 2407530368,
402415918976, 2424307328, 2432695424, 2441084288, 2449472384,
412457861248, 2466247808, 2474637184, 2483026816, 2491414144,
422499803776, 2508191872, 2516582272, 2524970368, 2533359232,
432541743488, 2550134144, 2558525056, 2566913408, 2575301504,
442583686528, 2592073856, 2600467328, 2608856192, 2617240448,
452625631616, 2634022016, 2642407552, 2650796416, 2659188352,
462667574912, 2675965312, 2684352896, 2692738688, 2701130624,
472709518464, 2717907328, 2726293376, 2734685056, 2743073152,
482751462016, 2759851648, 2768232832, 2776625536, 2785017728,
492793401984, 2801794432, 2810182016, 2818571648, 2826959488,
502835349376, 2843734144, 2852121472, 2860514432, 2868900992,
512877286784, 2885676928, 2894069632, 2902451584, 2910843008,
522919234688, 2927622784, 2936011648, 2944400768, 2952789376,
532961177728, 2969565568, 2977951616, 2986338944, 2994731392,
543003120256, 3011508352, 3019895936, 3028287104, 3036675968,
553045063808, 3053452928, 3061837696, 3070228352, 3078615424,
563087003776, 3095394944, 3103782272, 3112173184, 3120562048,
573128944768, 3137339264, 3145725056, 3154109312, 3162505088,
583170893184, 3179280256, 3187669376, 3196056704, 3204445568,
593212836736, 3221224064, 3229612928, 3238002304, 3246391168,
603254778496, 3263165824, 3271556224, 3279944576, 3288332416,
613296719232, 3305110912, 3313500032, 3321887104, 3330273152,
623338658944, 3347053184, 3355440512, 3363827072, 3372220288,
633380608384, 3388997504, 3397384576, 3405774208, 3414163072,
643422551936, 3430937984, 3439328384, 3447714176, 3456104576,
653464493952, 3472883584, 3481268864, 3489655168, 3498048896,
663506434432, 3514826368, 3523213952, 3531603584, 3539987072,
673548380288, 3556763264, 3565157248, 3573545344, 3581934464,
683590324096, 3598712704, 3607098752, 3615488384, 3623877248,
693632265856, 3640646528, 3649043584, 3657430144, 3665821568,
703674207872, 3682597504, 3690984832, 3699367808, 3707764352,
713716152448, 3724541056, 3732925568, 3741318016, 3749706368,
723758091136, 3766481536, 3774872704, 3783260032, 3791650432,
733800036224, 3808427648, 3816815488, 3825204608, 3833592704,
743841981568, 3850370432, 3858755968, 3867147904, 3875536256,
753883920512, 3892313728, 3900702592, 3909087872, 3917478784,
763925868416, 3934256512, 3942645376, 3951032192, 3959422336,
773967809152, 3976200064, 3984588416, 3992974976, 4001363584,
784009751168, 4018141312, 4026530432, 4034911616, 4043308928,
794051695488, 4060084352, 4068472448, 4076862848, 4085249408,
804093640576, 4102028416, 4110413696, 4118805632, 4127194496,
814135583104, 4143971968, 4152360832, 4160746112, 4169135744,
824177525888, 4185912704, 4194303616, 4202691968, 4211076736,
834219463552, 4227855488, 4236246656, 4244633728, 4253022848,
844261412224, 4269799808, 4278184832, 4286578048, 4294962304,
854303349632, 4311743104, 4320130432, 4328521088, 4336909184,
864345295488, 4353687424, 4362073472, 4370458496, 4378852736,
874387238528, 4395630208, 4404019072, 4412407424, 4420790656,
884429182848, 4437571456, 4445962112, 4454344064, 4462738048,
894471119232, 4479516544, 4487904128, 4496289664, 4504682368,
904513068416, 4521459584, 4529846144, 4538232704, 4546619776,
914555010176, 4563402112, 4571790208, 4580174464, 4588567936,
924596957056, 4605344896, 4613734016, 4622119808, 4630511488,
934638898816, 4647287936, 4655675264, 4664065664, 4672451968,
944680842624, 4689231488, 4697620352, 4706007424, 4714397056,
954722786176, 4731173248, 4739562368, 4747951744, 4756340608,
964764727936, 4773114496, 4781504384, 4789894784, 4798283648,
974806667648, 4815059584, 4823449472, 4831835776, 4840226176,
984848612224, 4857003392, 4865391488, 4873780096, 4882169728,
994890557312, 4898946944, 4907333248, 4915722368, 4924110976,
1004932499328, 4940889728, 4949276032, 4957666432, 4966054784,
1014974438016, 4982831488, 4991221376, 4999607168, 5007998848,
1025016386432, 5024763776, 5033164672, 5041544576, 5049941888,
1035058329728, 5066717056, 5075107456, 5083494272, 5091883904,
1045100273536, 5108662144, 5117048192, 5125436032, 5133827456,
1055142215296, 5150605184, 5158993024, 5167382144, 5175769472,
1065184157568, 5192543872, 5200936064, 5209324928, 5217711232,
1075226102656, 5234490496, 5242877312, 5251263872, 5259654016,
1085268040832, 5276434304, 5284819328, 5293209728, 5301598592,
1095309986688, 5318374784, 5326764416, 5335151488, 5343542144,
1105351929472, 5360319872, 5368706944, 5377096576, 5385484928,
1115393871232, 5402263424, 5410650496, 5419040384, 5427426944,
1125435816576, 5444205952, 5452594816, 5460981376, 5469367936,
1135477760896, 5486148736, 5494536832, 5502925952, 5511315328,
1145519703424, 5528089984, 5536481152, 5544869504, 5553256064,
1155561645696, 5570032768, 5578423936, 5586811264, 5595193216,
1165603585408, 5611972736, 5620366208, 5628750464, 5637143936,
1175645528192, 5653921408, 5662310272, 5670694784, 5679082624,
1185687474048, 5695864448, 5704251008, 5712641408, 5721030272,
1195729416832, 5737806208, 5746194304, 5754583936, 5762969984,
1205771358592, 5779748224, 5788137856, 5796527488, 5804911232,
1215813300608, 5821692544, 5830082176, 5838468992, 5846855552,
1225855247488, 5863636096, 5872024448, 5880411008, 5888799872,
1235897186432, 5905576832, 5913966976, 5922352768, 5930744704,
1245939132288, 5947522432, 5955911296, 5964299392, 5972688256,
1255981074304, 5989465472, 5997851008, 6006241408, 6014627968,
1266023015552, 6031408256, 6039796096, 6048185216, 6056574848,
1276064963456, 6073351808, 6081736064, 6090128768, 6098517632,
1286106906496, 6115289216, 6123680896, 6132070016, 6140459648,
1296148849024, 6157237376, 6165624704, 6174009728, 6182403712,
1306190792064, 6199176064, 6207569792, 6215952256, 6224345216,
1316232732544, 6241124224, 6249510272, 6257899136, 6266287744,
1326274676864, 6283065728, 6291454336, 6299843456, 6308232064,
1336316620928, 6325006208, 6333395584, 6341784704, 6350174848,
1346358562176, 6366951296, 6375337856, 6383729536, 6392119168,
1356400504192, 6408895616, 6417283456, 6425673344, 6434059136,
1366442444672, 6450837376, 6459223424, 6467613056, 6476004224,
1376484393088, 6492781952, 6501170048, 6509555072, 6517947008,
1386526336384, 6534725504, 6543112832, 6551500672, 6559888768,
1396568278656, 6576662912, 6585055616, 6593443456, 6601834112,
1406610219648, 6618610304, 6626999168, 6635385472, 6643777408,
1416652164224, 6660552832, 6668941952, 6677330048, 6685719424,
1426694107776, 6702493568, 6710882176, 6719274112, 6727662976,
1436736052096, 6744437632, 6752825984, 6761213824, 6769604224,
1446777993856, 6786383488, 6794770816, 6803158144, 6811549312,
1456819937664, 6828326528, 6836706176, 6845101696, 6853491328,
1466861880448, 6870269312, 6878655104, 6887046272, 6895433344,
1476903822208, 6912212864, 6920596864, 6928988288, 6937377152,
1486945764992, 6954149248, 6962544256, 6970928768, 6979317376,
1496987709312, 6996093824, 7004487296, 7012875392, 7021258624,
1507029652352, 7038038912, 7046427776, 7054818944, 7063207808,
1517071595136, 7079980928, 7088372608, 7096759424, 7105149824,
1527113536896, 7121928064, 7130315392, 7138699648, 7147092352,
1537155479168, 7163865728, 7172249984, 7180648064, 7189036672,
1547197424768, 7205810816, 7214196608, 7222589824, 7230975104,
1557239367552, 7247755904, 7256145536, 7264533376, 7272921472,
1567281308032, 7289694848, 7298088832, 7306471808, 7314864512,
1577323253888, 7331643008, 7340029568, 7348419712, 7356808832,
1587365196672, 7373585792, 7381973888, 7390362752, 7398750592,
1597407138944, 7415528576, 7423915648, 7432302208, 7440690304,
1607449080192, 7457472128, 7465860992, 7474249088, 7482635648,
1617491023744, 7499412608, 7507803008, 7516192384, 7524579968,
1627532967296, 7541358464, 7549745792, 7558134656, 7566524032,
1637574912896, 7583300992, 7591690112, 7600075136, 7608466816,
1647616854912, 7625244544, 7633629824, 7642020992, 7650410368,
1657658794112, 7667187328, 7675574912, 7683961984, 7692349568,
1667700739712, 7709130368, 7717519232, 7725905536, 7734295424,
1677742683264, 7751069056, 7759457408, 7767849088, 7776238208,
1687784626816, 7793014912, 7801405312, 7809792128, 7818179968,
1697826571136, 7834957184, 7843347328, 7851732352, 7860124544,
1707868512384, 7876902016, 7885287808, 7893679744, 7902067072,
1717910455936, 7918844288, 7927230848, 7935622784, 7944009344,
1727952400256, 7960786048, 7969176704, 7977565312, 7985953408,
1737994339968, 8002730368, 8011119488, 8019508096, 8027896192,
1748036285056, 8044674688, 8053062272, 8061448832, 8069838464,
1758078227328, 8086616704, 8095006592, 8103393664, 8111783552,
1768120171392, 8128560256, 8136949376, 8145336704, 8153726848,
1778162114944, 8170503296, 8178891904, 8187280768, 8195669632,
1788204058496, 8212444544, 8220834176, 8229222272, 8237612672,
1798246000768, 8254389376, 8262775168, 8271167104, 8279553664,
1808287944064, 8296333184, 8304715136, 8313108352, 8321497984,
1818329885568, 8338274432, 8346663296, 8355052928, 8363441536,
1828371828352, 8380217984, 8388606592, 8396996224, 8405384576,
1838413772672, 8422161536, 8430549376, 8438939008, 8447326592,
1848455715456, 8464104832, 8472492928, 8480882048, 8489270656,
1858497659776, 8506045312, 8514434944, 8522823808, 8531208832,
1868539602304, 8547990656, 8556378752, 8564768384, 8573154176,
1878581542784, 8589933952, 8598322816, 8606705024, 8615099264,
1888623487872, 8631876992, 8640264064, 8648653952, 8657040256,
1898665430656, 8673820544, 8682209152, 8690592128, 8698977152,
1908707374464, 8715763328, 8724151424, 8732540032, 8740928384,
1918749315712, 8757704576, 8766089344, 8774480768, 8782871936,
1928791260032, 8799645824, 8808034432, 8816426368, 8824812928,
1938833199488, 8841591424, 8849976448, 8858366336, 8866757248,
1948875147136, 8883532928, 8891923328, 8900306816, 8908700288,
1958917088384, 8925478784, 8933867392, 8942250368, 8950644608,
1968959032704, 8967420544, 8975809664, 8984197504, 8992584064,
1979000976256, 9009362048, 9017752448, 9026141312, 9034530688,
1989042917504, 9051307904, 9059694208, 9068084864, 9076471424,
1999084861824, 9093250688, 9101638528, 9110027648, 9118416512,
2009126803584, 9135188096, 9143581312, 9151969664, 9160356224,
2019168747136, 9177134464, 9185525632, 9193910144, 9202302848,
2029210690688, 9219079552, 9227465344, 9235854464, 9244244864,
2039252633472, 9261021824, 9269411456, 9277799296, 9286188928,
2049294574208, 9302965888, 9311351936, 9319740032, 9328131968,
2059336516736, 9344907392, 9353296768, 9361685888, 9370074752,
2069378463616, 9386849408, 9395239808, 9403629184, 9412016512,
2079420405376, 9428795008, 9437181568, 9445570688, 9453960832,
2089462346624, 9470738048, 9479121536, 9487515008, 9495903616,
2099504289664, 9512678528, 9521067904, 9529456256, 9537843584,
2109546233728, 9554621312, 9563011456, 9571398784, 9579788672,
2119588178304, 9596567168, 9604954496, 9613343104, 9621732992,
2129630121856, 9638508416, 9646898816, 9655283584, 9663675776,
2139672061312, 9680449664, 9688840064, 9697230464, 9705617536,
2149714003584, 9722393984, 9730772608, 9739172224, 9747561088,
2159755945344, 9764338816, 9772726144, 9781116544, 9789503872,
2169797892992, 9806282624, 9814670464, 9823056512, 9831439232,
2179839833984, 9848224384, 9856613504, 9865000576, 9873391232,
2189881772416, 9890162816, 9898556288, 9906940544, 9915333248,
2199923721088, 9932108672, 9940496512, 9948888448, 9957276544,
2209965666176, 9974048384, 9982441088, 9990830464, 9999219584,
22110007602816, 10015996544, 10024385152, 10032774016, 10041163648,
22210049548928, 10057940096, 10066329472, 10074717824, 10083105152,
22310091495296, 10099878784, 10108272256, 10116660608, 10125049216,
22410133437312, 10141825664, 10150213504, 10158601088, 10166991232,
22510175378816, 10183766144, 10192157312, 10200545408, 10208935552,
22610217322112, 10225712768, 10234099328, 10242489472, 10250876032,
22710259264896, 10267656064, 10276042624, 10284429184, 10292820352,
22810301209472, 10309598848, 10317987712, 10326375296, 10334763392,
22910343153536, 10351541632, 10359930752, 10368318592, 10376707456,
23010385096576, 10393484672, 10401867136, 10410262144, 10418647424,
23110427039104, 10435425664, 10443810176, 10452203648, 10460589952,
23210468982144, 10477369472, 10485759104, 10494147712, 10502533504,
23310510923392, 10519313536, 10527702656, 10536091264, 10544478592,
23410552867712, 10561255808, 10569642368, 10578032768, 10586423168,
23510594805632, 10603200128, 10611588992, 10619976064, 10628361344,
23610636754048, 10645143424, 10653531776, 10661920384, 10670307968,
23710678696832, 10687086464, 10695475072, 10703863168, 10712246144,
23810720639616, 10729026688, 10737414784, 10745806208, 10754190976,
23910762581376, 10770971264, 10779356288, 10787747456, 10796135552,
24010804525184, 10812915584, 10821301888, 10829692288, 10838078336,
24110846469248, 10854858368, 10863247232, 10871631488, 10880023424,
24210888412032, 10896799616, 10905188992, 10913574016, 10921964672,
24310930352768, 10938742912, 10947132544, 10955518592, 10963909504,
24410972298368, 10980687488, 10989074816, 10997462912, 11005851776,
24511014241152, 11022627712, 11031017344, 11039403904, 11047793024,
24611056184704, 11064570752, 11072960896, 11081343872, 11089737856,
24711098128256, 11106514816, 11114904448, 11123293568, 11131680128,
24811140065152, 11148458368, 11156845696, 11165236864, 11173624192,
24911182013824, 11190402688, 11198790784, 11207179136, 11215568768,
25011223957376, 11232345728, 11240734592, 11249122688, 11257511296,
25111265899648, 11274285952, 11282675584, 11291065472, 11299452544,
25211307842432, 11316231296, 11324616832, 11333009024, 11341395584,
25311349782656, 11358172288, 11366560384, 11374950016, 11383339648,
25411391721856, 11400117376, 11408504192, 11416893568, 11425283456,
25511433671552, 11442061184, 11450444672, 11458837888, 11467226752,
25611475611776, 11484003968, 11492392064, 11500780672, 11509169024,
25711517550976, 11525944448, 11534335616, 11542724224, 11551111808,
25811559500672, 11567890304, 11576277376, 11584667008, 11593056128,
25911601443456, 11609830016, 11618221952, 11626607488, 11634995072,
26011643387776, 11651775104, 11660161664, 11668552576, 11676940928,
26111685330304, 11693718656, 11702106496, 11710496128, 11718882688,
26211727273088, 11735660416, 11744050048, 11752437376, 11760824704,
26311769216128, 11777604736, 11785991296, 11794381952, 11802770048,
26411811157888, 11819548544, 11827932544, 11836324736, 11844713344,
26511853100928, 11861486464, 11869879936, 11878268032, 11886656896,
26611895044992, 11903433088, 11911822976, 11920210816, 11928600448,
26711936987264, 11945375872, 11953761152, 11962151296, 11970543488,
26811978928512, 11987320448, 11995708288, 12004095104, 12012486272,
26912020875136, 12029255552, 12037652096, 12046039168, 12054429568,
27012062813824, 12071206528, 12079594624, 12087983744, 12096371072,
27112104759936, 12113147264, 12121534592, 12129924992, 12138314624,
27212146703232, 12155091584, 12163481216, 12171864704, 12180255872,
27312188643968, 12197034112, 12205424512, 12213811328, 12222199424,
27412230590336, 12238977664, 12247365248, 12255755392, 12264143488,
27512272531584, 12280920448, 12289309568, 12297694592, 12306086528,
27612314475392, 12322865024, 12331253632, 12339640448, 12348029312,
27712356418944, 12364805248, 12373196672, 12381580928, 12389969024,
27812398357632, 12406750592, 12415138432, 12423527552, 12431916416,
27912440304512, 12448692352, 12457081216, 12465467776, 12473859968,
28012482245504, 12490636672, 12499025536, 12507411584, 12515801728,
28112524190592, 12532577152, 12540966272, 12549354368, 12557743232,
28212566129536, 12574523264, 12582911872, 12591299456, 12599688064,
28312608074624, 12616463488, 12624845696, 12633239936, 12641631616,
28412650019968, 12658407296, 12666795136, 12675183232, 12683574656,
28512691960192, 12700350592, 12708740224, 12717128576, 12725515904,
28612733906816, 12742295168, 12750680192, 12759071872, 12767460736,
28712775848832, 12784236928, 12792626816, 12801014656, 12809404288,
28812817789312, 12826181504, 12834568832, 12842954624, 12851345792,
28912859732352, 12868122496, 12876512128, 12884901248, 12893289088,
29012901672832, 12910067584, 12918455168, 12926842496, 12935232896,
29112943620736, 12952009856, 12960396928, 12968786816, 12977176192,
29212985563776, 12993951104, 13002341504, 13010730368, 13019115392,
29313027506304, 13035895168, 13044272512, 13052673152, 13061062528,
29413069446272, 13077838976, 13086227072, 13094613632, 13103000192,
29513111393664, 13119782528, 13128157568, 13136559232, 13144945024,
29613153329536, 13161724288, 13170111872, 13178502784, 13186884736,
29713195279744, 13203667072, 13212057472, 13220445824, 13228832128,
29813237221248, 13245610624, 13254000512, 13262388352, 13270777472,
29913279166336, 13287553408, 13295943296, 13304331904, 13312719488,
30013321108096, 13329494656, 13337885824, 13346274944, 13354663808,
30113363051136, 13371439232, 13379825024, 13388210816, 13396605056,
30213404995456, 13413380224, 13421771392, 13430159744, 13438546048,
30313446937216, 13455326848, 13463708288, 13472103808, 13480492672,
30413488875648, 13497269888, 13505657728, 13514045312, 13522435712,
30513530824576, 13539210112, 13547599232, 13555989376, 13564379008,
30613572766336, 13581154432, 13589544832, 13597932928, 13606320512,
30713614710656, 13623097472, 13631477632, 13639874944, 13648264064,
30813656652928, 13665041792, 13673430656, 13681818496, 13690207616,
30913698595712, 13706982272, 13715373184, 13723762048, 13732150144,
31013740536704, 13748926592, 13757316224, 13765700992, 13774090112,
31113782477952, 13790869376, 13799259008, 13807647872, 13816036736,
31213824425344, 13832814208, 13841202304, 13849591424, 13857978752,
31313866368896, 13874754688, 13883145344, 13891533184, 13899919232,
31413908311168, 13916692096, 13925085056, 13933473152, 13941866368,
31513950253696, 13958643584, 13967032192, 13975417216, 13983807616,
31613992197504, 14000582272, 14008973696, 14017363072, 14025752192,
31714034137984, 14042528384, 14050918016, 14059301504, 14067691648,
31814076083584, 14084470144, 14092852352, 14101249664, 14109635968,
31914118024832, 14126407552, 14134804352, 14143188608, 14151577984,
32014159968384, 14168357248, 14176741504, 14185127296, 14193521024,
32114201911424, 14210301824, 14218685056, 14227067264, 14235467392,
32214243855488, 14252243072, 14260630144, 14269021568, 14277409408,
32314285799296, 14294187904, 14302571392, 14310961792, 14319353728,
32414327738752, 14336130944, 14344518784, 14352906368, 14361296512,
32514369685376, 14378071424, 14386462592, 14394848128, 14403230848,
32614411627392, 14420013952, 14428402304, 14436793472, 14445181568,
32714453569664, 14461959808, 14470347904, 14478737024, 14487122816,
32814495511424, 14503901824, 14512291712, 14520677504, 14529064832,
32914537456768, 14545845632, 14554234496, 14562618496, 14571011456,
33014579398784, 14587789184, 14596172672, 14604564608, 14612953984,
33114621341312, 14629724288, 14638120832, 14646503296, 14654897536,
33214663284864, 14671675264, 14680061056, 14688447616, 14696835968,
33314705228416, 14713616768, 14722003328, 14730392192, 14738784128,
33414747172736, 14755561088, 14763947648, 14772336512, 14780725376,
33514789110144, 14797499776, 14805892736, 14814276992, 14822670208,
33614831056256, 14839444352, 14847836032, 14856222848, 14864612992,
33714872997504, 14881388672, 14889775744, 14898165376, 14906553472,
33814914944896, 14923329664, 14931721856, 14940109696, 14948497024,
33914956887424, 14965276544, 14973663616, 14982053248, 14990439808,
34014998830976, 15007216768, 15015605888, 15023995264, 15032385152,
34115040768384, 15049154944, 15057549184, 15065939072, 15074328448,
34215082715008, 15091104128, 15099493504, 15107879296, 15116269184,
34315124659584, 15133042304, 15141431936, 15149824384, 15158214272,
34415166602368, 15174991232, 15183378304, 15191760512, 15200154496,
34515208542592, 15216931712, 15225323392, 15233708416, 15242098048,
34615250489216, 15258875264, 15267265408, 15275654528, 15284043136,
34715292431488, 15300819584, 15309208192, 15317596544, 15325986176,
34815334374784, 15342763648, 15351151744, 15359540608, 15367929728,
34915376318336, 15384706432, 15393092992, 15401481856, 15409869952,
35015418258816, 15426649984, 15435037568, 15443425664, 15451815296,
35115460203392, 15468589184, 15476979328, 15485369216, 15493755776,
35215502146944, 15510534272, 15518924416, 15527311232, 15535699072,
35315544089472, 15552478336, 15560866688, 15569254528, 15577642624,
35415586031488, 15594419072, 15602809472, 15611199104, 15619586432,
35515627975296, 15636364928, 15644753792, 15653141888, 15661529216,
35615669918848, 15678305152, 15686696576, 15695083136, 15703474048,
35715711861632, 15720251264, 15728636288, 15737027456, 15745417088,
35815753804928, 15762194048, 15770582656, 15778971008, 15787358336,
35915795747712, 15804132224, 15812523392, 15820909696, 15829300096,
36015837691264, 15846071936, 15854466944, 15862855808, 15871244672,
36115879634816, 15888020608, 15896409728, 15904799104, 15913185152,
36215921577088, 15929966464, 15938354816, 15946743424, 15955129472,
36315963519872, 15971907968, 15980296064, 15988684928, 15997073024,
36416005460864, 16013851264, 16022241152, 16030629248, 16039012736,
36516047406976, 16055794816, 16064181376, 16072571264, 16080957824,
36616089346688, 16097737856, 16106125184, 16114514816, 16122904192,
36716131292544, 16139678848, 16148066944, 16156453504, 16164839552,
36816173236096, 16181623424, 16190012032, 16198401152, 16206790528,
36916215177344, 16223567744, 16231956352, 16240344704, 16248731008,
37016257117824, 16265504384, 16273898624, 16282281856, 16290668672,
37116299064192, 16307449216, 16315842176, 16324230016, 16332613504,
37216341006464, 16349394304, 16357783168, 16366172288, 16374561664,
37316382951296, 16391337856, 16399726208, 16408116352, 16416505472,
37416424892032, 16433282176, 16441668224, 16450058624, 16458448768,
37516466836864, 16475224448, 16483613056, 16492001408, 16500391808,
37616508779648, 16517166976, 16525555328, 16533944192, 16542330752,
37716550719616, 16559110528, 16567497088, 16575888512, 16584274816,
37816592665472, 16601051008, 16609442944, 16617832064, 16626218624,
37916634607488, 16642996096, 16651385728, 16659773824, 16668163712,
38016676552576, 16684938112, 16693328768, 16701718144, 16710095488,
38116718492288, 16726883968, 16735272832, 16743661184, 16752049792,
38216760436608, 16768827008, 16777214336, 16785599104, 16793992832,
38316802381696, 16810768768, 16819151744, 16827542656, 16835934848,
38416844323712, 16852711552, 16861101952, 16869489536, 16877876864,
38516886265728, 16894653056, 16903044736, 16911431296, 16919821696,
38616928207488, 16936592768, 16944987776, 16953375616, 16961763968,
38716970152832, 16978540928, 16986929536, 16995319168, 17003704448,
38817012096896, 17020481152, 17028870784, 17037262208, 17045649536,
38917054039936, 17062426496, 17070814336, 17079205504, 17087592064,
39017095978112, 17104369024, 17112759424, 17121147776, 17129536384,
39117137926016, 17146314368, 17154700928, 17163089792, 17171480192,
39217179864192, 17188256896, 17196644992, 17205033856, 17213423488,
39317221811072, 17230198912, 17238588032, 17246976896, 17255360384,
39417263754624, 17272143232, 17280530048, 17288918912, 17297309312,
39517305696384, 17314085504, 17322475136, 17330863744, 17339252096,
39617347640192, 17356026496, 17364413824, 17372796544, 17381190016,
39717389583488, 17397972608, 17406360704, 17414748544, 17423135872,
39817431527296, 17439915904, 17448303232, 17456691584, 17465081728,
39917473468288, 17481857408, 17490247552, 17498635904, 17507022464,
40017515409024, 17523801728, 17532189824, 17540577664, 17548966016,
40117557353344, 17565741184, 17574131584, 17582519168, 17590907008,
40217599296128, 17607687808, 17616076672, 17624455808, 17632852352,
40317641238656, 17649630848, 17658018944, 17666403968, 17674794112,
40417683178368, 17691573376, 17699962496, 17708350592, 17716739968,
40517725126528, 17733517184, 17741898112, 17750293888, 17758673024,
40617767070336, 17775458432, 17783848832, 17792236928, 17800625536,
40717809012352, 17817402752, 17825785984, 17834178944, 17842563968,
40817850955648, 17859344512, 17867732864, 17876119424, 17884511872,
40917892900224, 17901287296, 17909677696, 17918058112, 17926451072,
41017934843776, 17943230848, 17951609216, 17960008576, 17968397696,
41117976784256, 17985175424, 17993564032, 18001952128, 18010339712,
41218018728576, 18027116672, 18035503232, 18043894144, 18052283264,
41318060672128, 18069056384, 18077449856, 18085837184, 18094225792,
41418102613376, 18111004544, 18119388544, 18127781248, 18136170368,
41518144558976, 18152947328, 18161336192, 18169724288, 18178108544,
41618186498944, 18194886784, 18203275648, 18211666048, 18220048768,
41718228444544, 18236833408, 18245220736]
418
419cache_sizes = [
42016776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072,
42117693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088,
42218611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208,
42319529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968,
42420446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216,
42521364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104,
42622281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096,
42723198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112,
42824116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488,
42925034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096,
43025951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472,
43126869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744,
43227786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504,
43328700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752,
43429621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976,
43530538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248,
43631456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392,
43732372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768,
43833289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992,
43934208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984,
44035127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976,
44136044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656,
44236961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904,
44337879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672,
44438795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632,
44539713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032,
44640631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304,
44741547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912,
44842467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696,
44943382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432,
45044302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448,
45145219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208,
45246136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328,
45347053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936,
45447971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312,
45548889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712,
45649807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472,
45750724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848,
45851641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968,
45952557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576,
46053475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744,
46154394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248,
46255312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856,
46356228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488,
46457146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632,
46558064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984,
46658981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512,
46759897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968,
46860817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752,
46961733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512,
47062651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656,
47163569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392,
47264486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792,
47365402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296,
47466321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672,
47567239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304,
47668157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912,
47769074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184,
47869989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816,
47970907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168,
48071826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568,
48172744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944,
48273662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832,
48374579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544,
48475497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072,
48576414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832,
48677331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336,
48778249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664,
48879166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472,
48980084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848,
49081002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304,
49181919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984,
49282835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464,
49383753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608,
49484672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496,
49585589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112,
49686506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632,
49787424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264,
49888341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384,
49989259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376,
50090177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776,
50191093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384,
50292012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912,
50392926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136,
50493845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896,
50594764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016,
50695681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544,
50796599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536,
50897517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168,
50998434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928,
51099352384, 99482816, 99614272, 99745472, 99876416, 100007104,
511100138048, 100267072, 100401088, 100529984, 100662592, 100791872,
512100925248, 101056064, 101187392, 101317952, 101449408, 101580608,
513101711296, 101841728, 101973824, 102104896, 102235712, 102366016,
514102498112, 102628672, 102760384, 102890432, 103021888, 103153472,
515103284032, 103415744, 103545152, 103677248, 103808576, 103939648,
516104070976, 104201792, 104332736, 104462528, 104594752, 104725952,
517104854592, 104988608, 105118912, 105247808, 105381184, 105511232,
518105643072, 105774784, 105903296, 106037056, 106167872, 106298944,
519106429504, 106561472, 106691392, 106822592, 106954304, 107085376,
520107216576, 107346368, 107478464, 107609792, 107739712, 107872192,
521108003136, 108131392, 108265408, 108396224, 108527168, 108657344,
522108789568, 108920384, 109049792, 109182272, 109312576, 109444928,
523109572928, 109706944, 109837888, 109969088, 110099648, 110230976,
524110362432, 110492992, 110624704, 110755264, 110886208, 111017408,
525111148864, 111279296, 111410752, 111541952, 111673024, 111803456,
526111933632, 112066496, 112196416, 112328512, 112457792, 112590784,
527112715968, 112852672, 112983616, 113114944, 113244224, 113376448,
528113505472, 113639104, 113770304, 113901376, 114031552, 114163264,
529114294592, 114425536, 114556864, 114687424, 114818624, 114948544,
530115080512, 115212224, 115343296, 115473472, 115605184, 115736128,
531115867072, 115997248, 116128576, 116260288, 116391488, 116522944,
532116652992, 116784704, 116915648, 117046208, 117178304, 117308608,
533117440192, 117569728, 117701824, 117833024, 117964096, 118094656,
534118225984, 118357312, 118489024, 118617536, 118749632, 118882112,
535119012416, 119144384, 119275328, 119406016, 119537344, 119668672,
536119798464, 119928896, 120061376, 120192832, 120321728, 120454336,
537120584512, 120716608, 120848192, 120979136, 121109056, 121241408,
538121372352, 121502912, 121634752, 121764416, 121895744, 122027072,
539122157632, 122289088, 122421184, 122550592, 122682944, 122813888,
540122945344, 123075776, 123207488, 123338048, 123468736, 123600704,
541123731264, 123861952, 123993664, 124124608, 124256192, 124386368,
542124518208, 124649024, 124778048, 124911296, 125041088, 125173696,
543125303744, 125432896, 125566912, 125696576, 125829056, 125958592,
544126090304, 126221248, 126352832, 126483776, 126615232, 126746432,
545126876608, 127008704, 127139392, 127270336, 127401152, 127532224,
546127663552, 127794752, 127925696, 128055232, 128188096, 128319424,
547128449856, 128581312, 128712256, 128843584, 128973632, 129103808,
548129236288, 129365696, 129498944, 129629888, 129760832, 129892288,
549130023104, 130154048, 130283968, 130416448, 130547008, 130678336,
550130807616, 130939456, 131071552, 131202112, 131331776, 131464384,
551131594048, 131727296, 131858368, 131987392, 132120256, 132250816,
552132382528, 132513728, 132644672, 132774976, 132905792, 133038016,
553133168832, 133299392, 133429312, 133562048, 133692992, 133823296,
554133954624, 134086336, 134217152, 134348608, 134479808, 134607296,
555134741056, 134872384, 135002944, 135134144, 135265472, 135396544,
556135527872, 135659072, 135787712, 135921472, 136052416, 136182848,
557136313792, 136444864, 136576448, 136707904, 136837952, 136970048,
558137099584, 137232064, 137363392, 137494208, 137625536, 137755712,
559137887424, 138018368, 138149824, 138280256, 138411584, 138539584,
560138672832, 138804928, 138936128, 139066688, 139196864, 139328704,
561139460032, 139590208, 139721024, 139852864, 139984576, 140115776,
562140245696, 140376512, 140508352, 140640064, 140769856, 140902336,
563141032768, 141162688, 141294016, 141426496, 141556544, 141687488,
564141819584, 141949888, 142080448, 142212544, 142342336, 142474432,
565142606144, 142736192, 142868288, 142997824, 143129408, 143258944,
566143392448, 143523136, 143653696, 143785024, 143916992, 144045632,
567144177856, 144309184, 144440768, 144570688, 144701888, 144832448,
568144965056, 145096384, 145227584, 145358656, 145489856, 145620928,
569145751488, 145883072, 146011456, 146144704, 146275264, 146407232,
570146538176, 146668736, 146800448, 146931392, 147062336, 147193664,
571147324224, 147455936, 147586624, 147717056, 147848768, 147979456,
572148110784, 148242368, 148373312, 148503232, 148635584, 148766144,
573148897088, 149028416, 149159488, 149290688, 149420224, 149551552,
574149683136, 149814976, 149943616, 150076352, 150208064, 150338624,
575150470464, 150600256, 150732224, 150862784, 150993088, 151125952,
576151254976, 151388096, 151519168, 151649728, 151778752, 151911104,
577152042944, 152174144, 152304704, 152435648, 152567488, 152698816,
578152828992, 152960576, 153091648, 153222976, 153353792, 153484096,
579153616192, 153747008, 153878336, 154008256, 154139968, 154270912,
580154402624, 154533824, 154663616, 154795712, 154926272, 155057984,
581155188928, 155319872, 155450816, 155580608, 155712064, 155843392,
582155971136, 156106688, 156237376, 156367424, 156499264, 156630976,
583156761536, 156892352, 157024064, 157155008, 157284416, 157415872,
584157545536, 157677248, 157810496, 157938112, 158071744, 158203328,
585158334656, 158464832, 158596288, 158727616, 158858048, 158988992,
586159121216, 159252416, 159381568, 159513152, 159645632, 159776192,
587159906496, 160038464, 160169536, 160300352, 160430656, 160563008,
588160693952, 160822208, 160956352, 161086784, 161217344, 161349184,
589161480512, 161611456, 161742272, 161873216, 162002752, 162135872,
590162266432, 162397888, 162529216, 162660032, 162790976, 162922048,
591163052096, 163184576, 163314752, 163446592, 163577408, 163707968,
592163839296, 163969984, 164100928, 164233024, 164364224, 164494912,
593164625856, 164756672, 164887616, 165019072, 165150016, 165280064,
594165412672, 165543104, 165674944, 165805888, 165936832, 166067648,
595166198336, 166330048, 166461248, 166591552, 166722496, 166854208,
596166985408, 167116736, 167246656, 167378368, 167508416, 167641024,
597167771584, 167903168, 168034112, 168164032, 168295744, 168427456,
598168557632, 168688448, 168819136, 168951616, 169082176, 169213504,
599169344832, 169475648, 169605952, 169738048, 169866304, 169999552,
600170131264, 170262464, 170393536, 170524352, 170655424, 170782016,
601170917696, 171048896, 171179072, 171310784, 171439936, 171573184,
602171702976, 171835072, 171966272, 172097216, 172228288, 172359232,
603172489664, 172621376, 172747712, 172883264, 173014208, 173144512,
604173275072, 173407424, 173539136, 173669696, 173800768, 173931712,
605174063424, 174193472, 174325696, 174455744, 174586816, 174718912,
606174849728, 174977728, 175109696, 175242688, 175374272, 175504832,
607175636288, 175765696, 175898432, 176028992, 176159936, 176291264,
608176422592, 176552512, 176684864, 176815424, 176946496, 177076544,
609177209152, 177340096, 177470528, 177600704, 177731648, 177864256,
610177994816, 178126528, 178257472, 178387648, 178518464, 178650176,
611178781888, 178912064, 179044288, 179174848, 179305024, 179436736,
612179568448, 179698496, 179830208, 179960512, 180092608, 180223808,
613180354752, 180485696, 180617152, 180748096, 180877504, 181009984,
614181139264, 181272512, 181402688, 181532608, 181663168, 181795136,
615181926592, 182057536, 182190016, 182320192, 182451904, 182582336,
616182713792, 182843072, 182976064, 183107264, 183237056, 183368384,
617183494848, 183631424, 183762752, 183893824, 184024768, 184154816,
618184286656, 184417984, 184548928, 184680128, 184810816, 184941248,
619185072704, 185203904, 185335616, 185465408, 185596352, 185727296,
620185859904, 185989696, 186121664, 186252992, 186383552, 186514112,
621186645952, 186777152, 186907328, 187037504, 187170112, 187301824,
622187429184, 187562048, 187693504, 187825472, 187957184, 188087104,
623188218304, 188349376, 188481344, 188609728, 188743616, 188874304,
624189005248, 189136448, 189265088, 189396544, 189528128, 189660992,
625189791936, 189923264, 190054208, 190182848, 190315072, 190447424,
626190577984, 190709312, 190840768, 190971328, 191102656, 191233472,
627191364032, 191495872, 191626816, 191758016, 191888192, 192020288,
628192148928, 192282176, 192413504, 192542528, 192674752, 192805952,
629192937792, 193068608, 193198912, 193330496, 193462208, 193592384,
630193723456, 193854272, 193985984, 194116672, 194247232, 194379712,
631194508352, 194641856, 194772544, 194900672, 195035072, 195166016,
632195296704, 195428032, 195558592, 195690304, 195818176, 195952576,
633196083392, 196214336, 196345792, 196476736, 196607552, 196739008,
634196869952, 197000768, 197130688, 197262784, 197394368, 197523904,
635197656384, 197787584, 197916608, 198049472, 198180544, 198310208,
636198442432, 198573632, 198705088, 198834368, 198967232, 199097792,
637199228352, 199360192, 199491392, 199621696, 199751744, 199883968,
638200014016, 200146624, 200276672, 200408128, 200540096, 200671168,
639200801984, 200933312, 201062464, 201194944, 201326144, 201457472,
640201588544, 201719744, 201850816, 201981632, 202111552, 202244032,
641202374464, 202505152, 202636352, 202767808, 202898368, 203030336,
642203159872, 203292608, 203423296, 203553472, 203685824, 203816896,
643203947712, 204078272, 204208192, 204341056, 204472256, 204603328,
644204733888, 204864448, 204996544, 205125568, 205258304, 205388864,
645205517632, 205650112, 205782208, 205913536, 206044736, 206176192,
646206307008, 206434496, 206569024, 206700224, 206831168, 206961856,
647207093056, 207223616, 207355328, 207486784, 207616832, 207749056,
648207879104, 208010048, 208141888, 208273216, 208404032, 208534336,
649208666048, 208796864, 208927424, 209059264, 209189824, 209321792,
650209451584, 209582656, 209715136, 209845568, 209976896, 210106432,
651210239296, 210370112, 210501568, 210630976, 210763712, 210894272,
652211024832, 211156672, 211287616, 211418176, 211549376, 211679296,
653211812032, 211942592, 212074432, 212204864, 212334016, 212467648,
654212597824, 212727616, 212860352, 212991424, 213120832, 213253952,
655213385024, 213515584, 213645632, 213777728, 213909184, 214040128,
656214170688, 214302656, 214433728, 214564544, 214695232, 214826048,
657214956992, 215089088, 215219776, 215350592, 215482304, 215613248,
658215743552, 215874752, 216005312, 216137024, 216267328, 216399296,
659216530752, 216661696, 216790592, 216923968, 217054528, 217183168,
660217316672, 217448128, 217579072, 217709504, 217838912, 217972672,
661218102848, 218233024, 218364736, 218496832, 218627776, 218759104,
662218888896, 219021248, 219151936, 219281728, 219413056, 219545024,
663219675968, 219807296, 219938624, 220069312, 220200128, 220331456,
664220461632, 220592704, 220725184, 220855744, 220987072, 221117888,
665221249216, 221378368, 221510336, 221642048, 221772736, 221904832,
666222031808, 222166976, 222297536, 222428992, 222559936, 222690368,
667222820672, 222953152, 223083968, 223213376, 223345984, 223476928,
668223608512, 223738688, 223869376, 224001472, 224132672, 224262848,
669224394944, 224524864, 224657344, 224788288, 224919488, 225050432,
670225181504, 225312704, 225443776, 225574592, 225704768, 225834176,
671225966784, 226097216, 226229824, 226360384, 226491712, 226623424,
672226754368, 226885312, 227015104, 227147456, 227278528, 227409472,
673227539904, 227669696, 227802944, 227932352, 228065216, 228196288,
674228326464, 228457792, 228588736, 228720064, 228850112, 228981056,
675229113152, 229243328, 229375936, 229505344, 229636928, 229769152,
676229894976, 230030272, 230162368, 230292416, 230424512, 230553152,
677230684864, 230816704, 230948416, 231079616, 231210944, 231342016,
678231472448, 231603776, 231733952, 231866176, 231996736, 232127296,
679232259392, 232388672, 232521664, 232652608, 232782272, 232914496,
680233043904, 233175616, 233306816, 233438528, 233569984, 233699776,
681233830592, 233962688, 234092224, 234221888, 234353984, 234485312,
682234618304, 234749888, 234880832, 235011776, 235142464, 235274048,
683235403456, 235535936, 235667392, 235797568, 235928768, 236057152,
684236190272, 236322752, 236453312, 236583616, 236715712, 236846528,
685236976448, 237108544, 237239104, 237371072, 237501632, 237630784,
686237764416, 237895232, 238026688, 238157632, 238286912, 238419392,
687238548032, 238681024, 238812608, 238941632, 239075008, 239206336,
688239335232, 239466944, 239599168, 239730496, 239861312, 239992384,
689240122816, 240254656, 240385856, 240516928, 240647872, 240779072,
690240909632, 241040704, 241171904, 241302848, 241433408, 241565248,
691241696192, 241825984, 241958848, 242088256, 242220224, 242352064,
692242481856, 242611648, 242744896, 242876224, 243005632, 243138496,
693243268672, 243400384, 243531712, 243662656, 243793856, 243924544,
694244054592, 244187072, 244316608, 244448704, 244580032, 244710976,
695244841536, 244972864, 245104448, 245233984, 245365312, 245497792,
696245628736, 245759936, 245889856, 246021056, 246152512, 246284224,
697246415168, 246545344, 246675904, 246808384, 246939584, 247070144,
698247199552, 247331648, 247463872, 247593536, 247726016, 247857088,
699247987648, 248116928, 248249536, 248380736, 248512064, 248643008,
700248773312, 248901056, 249036608, 249167552, 249298624, 249429184,
701249560512, 249692096, 249822784, 249954112, 250085312, 250215488,
702250345792, 250478528, 250608704, 250739264, 250870976, 251002816,
703251133632, 251263552, 251395136, 251523904, 251657792, 251789248,
704251919424, 252051392, 252182464, 252313408, 252444224, 252575552,
705252706624, 252836032, 252968512, 253099712, 253227584, 253361728,
706253493056, 253623488, 253754432, 253885504, 254017216, 254148032,
707254279488, 254410432, 254541376, 254672576, 254803264, 254933824,
708255065792, 255196736, 255326528, 255458752, 255589952, 255721408,
709255851072, 255983296, 256114624, 256244416, 256374208, 256507712,
710256636096, 256768832, 256900544, 257031616, 257162176, 257294272,
711257424448, 257555776, 257686976, 257818432, 257949632, 258079552,
712258211136, 258342464, 258473408, 258603712, 258734656, 258867008,
713258996544, 259127744, 259260224, 259391296, 259522112, 259651904,
714259784384, 259915328, 260045888, 260175424, 260308544, 260438336,
715260570944, 260700992, 260832448, 260963776, 261092672, 261226304,
716261356864, 261487936, 261619648, 261750592, 261879872, 262011968,
717262143424, 262274752, 262404416, 262537024, 262667968, 262799296,
718262928704, 263061184, 263191744, 263322944, 263454656, 263585216,
719263716672, 263847872, 263978944, 264108608, 264241088, 264371648,
720264501184, 264632768, 264764096, 264895936, 265024576, 265158464,
721265287488, 265418432, 265550528, 265681216, 265813312, 265943488,
722266075968, 266206144, 266337728, 266468032, 266600384, 266731072,
723266862272, 266993344, 267124288, 267255616, 267386432, 267516992,
724267648704, 267777728, 267910592, 268040512, 268172096, 268302784,
725268435264, 268566208, 268696256, 268828096, 268959296, 269090368,
726269221312, 269352256, 269482688, 269614784, 269745856, 269876416,
727270007616, 270139328, 270270272, 270401216, 270531904, 270663616,
728270791744, 270924736, 271056832, 271186112, 271317184, 271449536,
729271580992, 271711936, 271843136, 271973056, 272105408, 272236352,
730272367296, 272498368, 272629568, 272759488, 272891456, 273022784,
731273153856, 273284672, 273415616, 273547072, 273677632, 273808448,
732273937088, 274071488, 274200896, 274332992, 274463296, 274595392,
733274726208, 274857536, 274988992, 275118656, 275250496, 275382208,
734275513024, 275643968, 275775296, 275906368, 276037184, 276167872,
735276297664, 276429376, 276560576, 276692672, 276822976, 276955072,
736277085632, 277216832, 277347008, 277478848, 277609664, 277740992,
737277868608, 278002624, 278134336, 278265536, 278395328, 278526784,
738278657728, 278789824, 278921152, 279052096, 279182912, 279313088,
739279443776, 279576256, 279706048, 279838528, 279969728, 280099648,
740280230976, 280361408, 280493632, 280622528, 280755392, 280887104,
741281018176, 281147968, 281278912, 281411392, 281542592, 281673152,
742281803712, 281935552, 282066496, 282197312, 282329024, 282458816,
743282590272, 282720832, 282853184, 282983744, 283115072, 283246144,
744283377344, 283508416, 283639744, 283770304, 283901504, 284032576,
745284163136, 284294848, 284426176, 284556992, 284687296, 284819264,
746284950208, 285081536]
Mostra tutto
 Copia