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