Ethash

Ethash era l'algoritmo di mining di prova di lavoro di Ethereum. La prova di lavoro è stata ora completamente disattivata ed Ethereum è ora protetto utilizzando invece la prova di stake. Scopri di più su The Merge, la prova di stake e lo staking. Questa pagina è di interesse storico!

Ethash è una versione modificata dell'algoritmo Dagger-Hashimoto. La prova di lavoro di Ethash è memory hard (opens in a new tab) (difficile per la memoria), il che si pensava rendesse l'algoritmo resistente agli ASIC. Alla fine sono stati sviluppati ASIC per Ethash, ma il mining con GPU è rimasto un'opzione praticabile fino a quando la prova di lavoro non è stata disattivata. Ethash è ancora utilizzato per minare altre monete su altre reti di prova di lavoro non di Ethereum.

Come funziona Ethash?

La difficoltà per la memoria è ottenuta con un algoritmo di prova di lavoro che richiede la scelta di sottoinsiemi di una risorsa fissa dipendente dal nonce e dall'intestazione del blocco. Questa risorsa (della dimensione di alcuni gigabyte) è chiamata DAG. Il DAG viene modificato ogni 30000 blocchi, una finestra di circa 125 ore chiamata epoca (circa 5,2 giorni) e richiede un po' di tempo per essere generato. Poiché il DAG dipende solo dall'altezza del blocco, può essere pre-generato, ma se non lo è, il client deve attendere la fine di questo processo per produrre un blocco. Se i client non pre-generano e memorizzano nella cache i DAG in anticipo, la rete potrebbe subire un massiccio ritardo dei blocchi a ogni transizione di epoca. Si noti che il DAG non deve essere generato per verificare la prova di lavoro, consentendo essenzialmente la verifica con CPU e memoria ridotte.

Il percorso generale seguito dall'algoritmo è il seguente:

Esiste un seme (seed) che può essere calcolato per ogni blocco scansionando le intestazioni dei blocchi fino a quel punto.
Dal seme, si può calcolare una cache pseudocasuale di 16 MB. I client leggeri memorizzano la cache.
Dalla cache, possiamo generare un set di dati di 1 GB, con la proprietà che ogni elemento nel set di dati dipende solo da un piccolo numero di elementi della cache. I client completi e i minatori memorizzano il set di dati. Il set di dati cresce linearmente nel tempo.
Il mining comporta il prelievo di porzioni casuali del set di dati e il loro hashing insieme. La verifica può essere eseguita con poca memoria utilizzando la cache per rigenerare i pezzi specifici del set di dati di cui si ha bisogno, quindi è necessario memorizzare solo la cache.

Il grande set di dati viene aggiornato una volta ogni 30000 blocchi, quindi la stragrande maggioranza dello sforzo di un minatore consisterà nel leggere il set di dati, non nell'apportarvi modifiche.

Definizioni

Impieghiamo 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 ha coinciso con lo sviluppo dello standard SHA3 e il processo di standardizzazione ha apportato una modifica tardiva al riempimento (padding) dell'algoritmo di hash finalizzato, in modo che gli hash "sha3_256" e "sha3_512" di Ethereum non siano hash sha3 standard, ma una variante spesso indicata come "Keccak-256" e "Keccak-512" in altri contesti. Vedi la discussione, ad es., qui (opens in a new tab), qui (opens in a new tab) o qui (opens in a new tab).

Tienilo a mente poiché gli hash "sha3" sono menzionati nella descrizione dell'algoritmo di seguito.

Parametri

I parametri per la cache e il set di dati di Ethash dipendono dal numero del blocco. La dimensione della cache e la dimensione del set di dati crescono entrambe linearmente; tuttavia, prendiamo sempre il numero primo più alto al di sotto della soglia di crescita lineare per ridurre il rischio di regolarità accidentali che portano a comportamenti ciclici.

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

Le tabelle dei valori delle dimensioni del set di dati e della cache sono fornite nell'appendice.

Generazione della cache

Ora, specifichiamo la funzione per produrre una cache:

1def mkcache(cache_size, seed):
2    n = cache_size // HASH_BYTES
3
4    # Produci sequenzialmente il dataset iniziale
5    o = [sha3_512(seed)]
6    for i in range(1, n):
7        o.append(sha3_512(o[-1]))
8
9    # Usa una versione con pochi round di 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

Il processo di produzione della cache prevede prima il riempimento sequenziale di 32 MB di memoria, quindi 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 è un insieme di 524288 valori da 64 byte.

Funzione di aggregazione dei dati

Utilizziamo un algoritmo ispirato all'hash FNV (opens in a new tab) in alcuni casi come sostituto non associativo per lo XOR. Si noti che moltiplichiamo il numero primo con l'intero input a 32 bit, in contrasto con le specifiche FNV-1 che moltiplicano il numero primo con un byte (ottetto) alla volta.

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

Si prega di notare che, sebbene lo yellow paper specifichi fnv come v1*(FNV_PRIME ^ v2), tutte le implementazioni attuali utilizzano coerentemente la definizione di cui sopra.

Calcolo del set di dati completo

Ogni elemento da 64 byte nel set di dati completo da 1 GB viene calcolato come segue:

1def calc_dataset_item(cache, i):
2    n = len(cache)
3    r = HASH_BYTES // WORD_BYTES
4    # inizializza il mix
5    mix = copy.copy(cache[i % n])
6    mix[0] ^= i
7    mix = sha3_512(mix)
8    # applica fnv con molti nodi di cache casuali basati su 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

Essenzialmente, combiniamo i dati da 256 nodi della cache selezionati in modo pseudocasuale e ne facciamo l'hash per calcolare il nodo del set di dati. L'intero set di dati viene quindi generato da:

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

Ciclo principale

Ora, specifichiamo il ciclo principale in stile "hashimoto", in cui aggreghiamo i dati dal set di dati completo per produrre il nostro valore finale per una particolare intestazione e nonce. Nel codice sottostante, header rappresenta l'hash SHA3-256 della rappresentazione RLP di un'intestazione di blocco troncata, ovvero di un'intestazione che esclude i campi mixHash e nonce. nonce sono gli otto byte di un intero senza segno a 64 bit in ordine big-endian. Quindi nonce[::-1] è la rappresentazione little-endian a 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    # combina header+nonce in un seed da 64 byte
6    s = sha3_512(header + nonce[::-1])
7    # inizia il mix con s replicato
8    mix = []
9    for _ in range(MIX_BYTES / HASH_BYTES):
10        mix.extend(s)
11    # mescola nodi casuali del dataset
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    # comprimi il 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

Essenzialmente, manteniamo un "mix" largo 128 byte e recuperiamo ripetutamente in modo sequenziale 128 byte dal set di dati completo e utilizziamo la funzione fnv per combinarlo con il mix. Vengono utilizzati 128 byte di accesso sequenziale in modo che ogni round dell'algoritmo recuperi sempre un'intera pagina dalla RAM, riducendo al minimo i mancati riscontri nel translation lookaside buffer (TLB) che gli ASIC sarebbero teoricamente in grado di evitare.

Se l'output di questo algoritmo è inferiore all'obiettivo desiderato, allora il nonce è valido. Si noti che l'applicazione aggiuntiva di sha3_256 alla fine garantisce l'esistenza di un nonce intermedio che può essere fornito per dimostrare che è stata eseguita almeno una piccola quantità di lavoro; questa rapida verifica esterna della prova di lavoro (PoW) può essere utilizzata per scopi anti-DDoS. Serve anche a fornire la garanzia statistica che il risultato sia un numero a 256 bit non distorto.

Mining

L'algoritmo di mining è definito come segue:

1def mine(full_size, dataset, header, difficulty):
2    # riempi di zeri il target per confrontarlo con l'hash sulla stessa cifra
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

Definizione dell'hash del seme

Per calcolare l'hash del seme che verrebbe utilizzato per minare sopra un dato blocco, utilizziamo 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

Si noti che per un mining e una verifica fluidi, si consiglia di pre-calcolare i futuri hash dei semi e i set di dati 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 a eseguire le specifiche python di cui sopra come codice.

1import sha3, copy
2
3# Presume un ordinamento dei bit little endian (lo stesso delle architetture Intel)
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# funzione di hash sha3, restituisce 64 byte
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

Dimensioni dei dati

Le seguenti tabelle di ricerca forniscono circa 2048 epoche tabulate di dimensioni dei dati e dimensioni 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