Ethash

Ethash était l'algorithme de minage par preuve de travail d'Ethereum. La preuve de travail est maintenant **arrêtée entièrement** et Ethereum est maintenant sécurisé en utilisant la preuve d'enjeu à la place. En savoir plus sur La Fusion, la preuve d'enjeu et la mise en jeu. Cette page n'a qu'un intérêt historique !

Ethash(opens in a new tab) est une version modifiée de l'algorithme Dagger-Hashimoto. La preuve de travail d'Ethash est une mémoire solide(opens in a new tab), qui était censée rendre l'algorithme ASIC plus résistant. Les Ethash ASIC ont finalement été développés, mais le minage via GPU restait encore une option viable jusqu’à ce que la preuve de travail soit désactivée. Ethash est toujours utilisé pour miner d'autres jetons sur des réseaux autres qu'Ethereum fonctionnant avec la preuve de travail.

Comment fonctionne Ethash ?

La complexité de la mémoire est obtenue avec un algorithme de preuve de travail qui nécessite de choisir des sous-ensembles d'une ressource donnée dépendant de l'en-tête du nonce et du bloc. Cette ressource (quelques gigaoctets de taille) est appelée DAG. Le DAG change tous les 30 000 blocs, une fenêtre de 125 heures appelée une époque (soit environ 5,2 jours) et prend un certain temps à se générer. Comme le DAG ne dépend que de la taille du bloc, il peut être pré-généré, mais si ce n'est pas le cas, le client doit attendre la fin de ce processus pour produire un bloc. Si les clients ne génèrent pas et ne mettent pas en cache les DAG à l'avance, le réseau peut rencontrer un retard dans la création de blocs pour chaque transition d'epoch. Notez que le DAG n'a pas besoin d'être généré pour vérifier la preuve de travail essentiellement en permettant la vérification à la fois avec un CPU lent et avec une mémoire réduite.

Le parcours habituel de l'algorithme est le suivant :

Il existe une graine qui peut être calculée pour chaque bloc en scannant les en-têtes de bloc jusqu'à ce point.
À partir de la graine, on peut calculer un cache pseudoaléatoire de 16 Mo. Les clients légers stockent le cache.
À partir du cache, nous pouvons générer un jeu de données 1 Go, avec la propriété que chaque élément du jeu de données ne dépend que d'un petit nombre d'éléments du cache. Les clients et les mineurs au complet stockent le jeu de données. Le jeu de données croît linéairement avec le temps.
Le minage consiste à saisir des tranches aléatoires de l'ensemble des données et à les hacher ensemble. La vérification peut être faite avec peu de mémoire en utilisant le cache pour régénérer les morceaux spécifiques du jeu de données dont vous avez besoin, ainsi, vous avez uniquement besoin de stocker le cache.

Le grand ensemble de données est mis à jour une fois tous les 30 000 blocs, de sorte que la grande majorité des efforts d'un mineur sera de lire l'ensemble des données, et non d'y apporter des modifications.

Définitions

Nous utilisons les définitions suivantes :

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
Afficher tout

L'utilisation de 'SHA3'

Le développement d'Ethereum a coïncidé avec le développement de la norme SHA3, et le processus de normes a réalisé un changement tardif dans le remplissage de l'algorithme de hachage finalisé de sorte que les hachages Ethereum "sha3_256" et "sha3_512" ne soient pas des hashs sha3 standard, mais une variante appelée souvent « Keccak-256 » et « Keccak-512 » dans d'autres contextes. Voir la discussion, par exemple ici(opens in a new tab), ici(opens in a new tab), ou ici(opens in a new tab).

Veuillez garder cela à l'esprit, car les hachages « sha3 » sont mentionnés dans la description de l'algorithme ci-dessous.

Paramètres

Les paramètres du cache et du jeu de données d'Ethash dépendent du numéro du bloc. La taille du cache et de la taille de l'ensemble des données augmentent linéairement ; cependant, nous prenons toujours le nombre premier le plus haut en dessous du seuil de croissance linéaire afin de réduire le risque de régularités accidentelles conduisant à un comportement cyclique.

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
Afficher tout
 Copier

Les tables de jeu de données et les valeurs de taille de cache sont fournies dans l'annexe.

Génération de cache

Maintenant, nous spécifions la fonction pour produire un 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
Afficher tout
 Copier

Le processus de production du cache implique d'abord le remplissage séquentiel de 32 Mo de mémoire, effectuant alors deux passes de l'algorithme RandMemoHash de Sergio Demian Lerner à partir de Strict Memory Hashing Functions (2014)(opens in a new tab). La sortie est un ensemble de valeurs de 524288 de 64 octets.

Fonction d'agrégation de données

Nous utilisons un algorithme inspiré du hachage FNV(opens in a new tab) dans certains cas comme un substitut non associatif pour XOR. Notez que nous multiplions le premier par l'entrée 32 bits, contrairement à la spécification FNV-1 qui multiplie le premier avec un octet à son tour.

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

Veuillez noter que même le papier jaune spécifie fnv comme v1*(FNV_PRIME ^ v2), toutes les implémentations actuelles utilisent systématiquement la définition ci-dessus.

Calcul du jeu de données complet

Chaque élément de 64 octets dans le jeu de données complet de 1 Go est calculé comme suit :

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)
Afficher tout
 Copier

Essentiellement, nous combinons des données à partir de 256 nœuds de cache sélectionnés de façon pseudologique, et de hachage pour calculer le noeud de l'ensemble de données. L'ensemble du jeu de données est ensuite généré par :

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

Boucle principale

Maintenant, nous spécifions la boucle principale « hashimoto », où nous agrégeons les données du jeu de données complet, afin de produire notre valeur finale pour un en-tête et un nonce. Dans le code ci-dessous, header représente le hachage SHA3-256 de la représentation RLP d'un en-tête de bloc tronqué, qui est d'un en-tête excluant les champs mixHash et nonce. nonce constitue les huit octets d'un entier 64 bits non signé dans un ordre big-endian. Ainsi nonce[::-1] est la représentation de huit octets little-endian de cette valeur :

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])
Afficher tout
 Copier

Essentiellement, nous maintenons un « mix » de 128 octets de taille, et récupérons séquentiellement 128 octets du jeu de données complet et utilisons la fonction fnv à des fins de combinaison avec le mix. 128 octets d'accès séquentiel sont utilisés de sorte que chaque tour de l'algorithme récupère toujours une page complète de la RAM. Minimiser le tampon de lecture de la traduction loupe ce que l'ASIC serait théoriquement en mesure d'éviter.

Si la sortie de cet algorithme est en dessous de la cible souhaitée, alors le nonce est valide. Notez que l'application supplémentaire de sha3_256 à la fin garantit qu'il existe un nonce intermédiaire qui peut être fourni pour prouver qu'au moins une petite quantité de travail a été faite ; cette vérification externe rapide de PoW peut être utilisée à des fins anti-DDoS. Cela sert également à fournir une assurance statistique que le résultat est un nombre non biaisé de 256 bits.

Minage

L'algorithme de minage est défini comme suit :

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
 Copier

Définition du hachage de la graine

Afin de calculer le hachage de la graine qui serait utilisé pour miner au-dessus d'un bloc donné, nous utilisons l'algorithme suivant :

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
 Copier

Notez que pour un minage et une vérification en douceur, nous recommandons de calculer au préalable les futures semences et les jeux de données dans un fil séparé.

Complément d'information

Une ressource communautaire vous a aidé ? Modifiez cette page et ajoutez-la !

Annexe

Le code suivant devrait être préfixé si vous souhaitez exécuter la spécification python ci-dessus en tant que code.

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
Afficher tout
 Copier

Tailles des données

Les tables de recherche suivantes fournissent environ 2048 epochs tabulées de la taille des données et de la taille des caches.

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]
Afficher tout
 Copier