--- title: Ethash description: Tinjauan mendetail tentang algoritma Ethash. lang: id --- Ethash adalah algoritma penambangan Bukti Kerja (PoW) Ethereum. Bukti Kerja (PoW) kini telah **dimatikan sepenuhnya** dan Ethereum sekarang diamankan menggunakan [Bukti Kepemilikan (PoS)](/developers/docs/consensus-mechanisms/pos/). Baca lebih lanjut tentang [The Merge](/roadmap/merge/), [Bukti Kepemilikan (PoS)](/developers/docs/consensus-mechanisms/pos/), dan [staking](/staking/). Halaman ini hanya untuk kepentingan sejarah! Ethash adalah versi modifikasi dari algoritma [Dagger-Hashimoto](/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms/dagger-hashimoto). Bukti Kerja (PoW) Ethash bersifat [memory hard](https://wikipedia.org/wiki/Memory-hard_function), yang dianggap membuat algoritma ini tahan terhadap ASIC. ASIC Ethash pada akhirnya dikembangkan tetapi penambangan GPU masih menjadi pilihan yang layak hingga Bukti Kerja (PoW) dimatikan. Ethash masih digunakan untuk menambang koin lain di jaringan Bukti Kerja (PoW) non-Ethereum lainnya. ## Bagaimana cara kerja Ethash? {#how-does-ethash-work} Sifat memory hard dicapai dengan algoritma Bukti Kerja (PoW) yang memerlukan pemilihan subset dari sumber daya tetap yang bergantung pada nonce dan header blok. Sumber daya ini (berukuran beberapa gigabita) disebut DAG. DAG diubah setiap 30000 blok, sebuah jendela waktu ~125 jam yang disebut Epok (sekitar 5,2 hari) dan membutuhkan waktu untuk dihasilkan. Karena DAG hanya bergantung pada tinggi blok, ia dapat dihasilkan sebelumnya, tetapi jika tidak, klien perlu menunggu hingga akhir proses ini untuk menghasilkan sebuah blok. Jika klien tidak menghasilkan sebelumnya dan menyimpan DAG dalam cache lebih awal, jaringan mungkin mengalami penundaan blok yang masif pada setiap transisi Epok. Perhatikan bahwa DAG tidak perlu dihasilkan untuk memverifikasi Bukti Kerja (PoW), yang pada dasarnya memungkinkan verifikasi dengan CPU rendah dan memori kecil. Rute umum yang diambil oleh algoritma ini adalah sebagai berikut: 1. Terdapat sebuah **seed** yang dapat dihitung untuk setiap blok dengan memindai melalui header blok hingga titik tersebut. 2. Dari seed tersebut, seseorang dapat menghitung **cache pseudorandom 16 MB**. Klien ringan menyimpan cache ini. 3. Dari cache tersebut, kita dapat menghasilkan **dataset 1 GB**, dengan properti bahwa setiap item dalam dataset hanya bergantung pada sejumlah kecil item dari cache. Klien penuh dan penambang menyimpan dataset ini. Dataset tumbuh secara linier seiring waktu. 4. Penambangan melibatkan pengambilan potongan acak dari dataset dan melakukan proses hash bersama-sama. Verifikasi dapat dilakukan dengan memori rendah dengan menggunakan cache untuk menghasilkan kembali bagian spesifik dari dataset yang Anda butuhkan, sehingga Anda hanya perlu menyimpan cache. Dataset besar diperbarui setiap 30000 blok, sehingga sebagian besar upaya penambang akan dihabiskan untuk membaca dataset, bukan membuat perubahan padanya. ## Definisi {#definitions} Kami menggunakan definisi berikut: ``` WORD_BYTES = 4 # byte dalam word DATASET_BYTES_INIT = 2**30 # byte dalam dataset pada genesis DATASET_BYTES_GROWTH = 2**23 # pertumbuhan dataset per Epok CACHE_BYTES_INIT = 2**24 # byte dalam cache pada genesis CACHE_BYTES_GROWTH = 2**17 # pertumbuhan cache per Epok CACHE_MULTIPLIER=1024 # Ukuran DAG relatif terhadap cache EPOCH_LENGTH = 30000 # blok per Epok MIX_BYTES = 128 # lebar mix HASH_BYTES = 64 # panjang hash dalam byte DATASET_PARENTS = 256 # jumlah induk dari setiap elemen dataset CACHE_ROUNDS = 3 # jumlah putaran dalam produksi cache ACCESSES = 64 # jumlah akses dalam loop hashimoto ``` ### Penggunaan 'SHA3' {#sha3} Pengembangan Ethereum bertepatan dengan pengembangan standar SHA3, dan proses standar tersebut membuat perubahan di akhir pada padding algoritma hash yang difinalisasi, sehingga hash "sha3_256" dan "sha3_512" Ethereum bukanlah hash sha3 standar, melainkan varian yang sering disebut sebagai "Keccak-256" dan "Keccak-512" dalam konteks lain. Lihat diskusi, mis., [di sini](https://eips.ethereum.org/EIPS/eip-1803), [di sini](https://ethereum.stackexchange.com/questions/550/which-cryptographic-hash-function-does-ethereum-use), atau [di sini](https://bitcoin.stackexchange.com/questions/42055/what-is-the-approach-to-calculate-an-ethereum-address-from-a-256-bit-private-key/42057#42057). Harap diingat hal tersebut karena hash "sha3" dirujuk dalam deskripsi algoritma di bawah ini. ## Parameter {#parameters} Parameter untuk cache dan dataset Ethash bergantung pada nomor blok. Ukuran cache dan ukuran dataset keduanya tumbuh secara linier; namun, kami selalu mengambil bilangan prima tertinggi di bawah ambang batas yang tumbuh secara linier untuk mengurangi risiko keteraturan yang tidak disengaja yang mengarah pada perilaku siklik. ```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 ``` Tabel nilai ukuran dataset dan cache disediakan di lampiran. ## Pembuatan cache {#cache-generation} Sekarang, kami menentukan fungsi untuk menghasilkan cache: ```python def mkcache(cache_size, seed): n = cache_size // HASH_BYTES # Hasilkan dataset awal secara berurutan o = [sha3_512(seed)] for i in range(1, n): o.append(sha3_512(o[-1])) # Gunakan versi putaran rendah dari 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 ``` Proses produksi cache melibatkan pengisian memori 32 MB secara berurutan terlebih dahulu, kemudian melakukan dua lintasan algoritma _RandMemoHash_ karya Sergio Demian Lerner dari [_Strict Memory Hard Hashing Functions_ (2014)](http://www.hashcash.org/papers/memohash.pdf). Outputnya adalah sekumpulan 524288 nilai 64-byte. ## Fungsi agregasi data {#date-aggregation-function} Kami menggunakan algoritma yang terinspirasi oleh [hash FNV](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function) dalam beberapa kasus sebagai pengganti non-asosiatif untuk XOR. Perhatikan bahwa kami mengalikan bilangan prima dengan input 32-bit penuh, berbeda dengan spesifikasi FNV-1 yang mengalikan bilangan prima dengan satu byte (oktet) secara bergantian. ```python FNV_PRIME = 0x01000193 def fnv(v1, v2): return ((v1 * FNV_PRIME) ^ v2) % 2**32 ``` Harap dicatat, meskipun kertas kuning menentukan fnv sebagai v1\*(FNV_PRIME ^ v2), semua implementasi saat ini secara konsisten menggunakan definisi di atas. ## Perhitungan dataset penuh {#full-dataset-calculation} Setiap item 64-byte dalam dataset penuh 1 GB dihitung sebagai berikut: ```python def calc_dataset_item(cache, i): n = len(cache) r = HASH_BYTES // WORD_BYTES # inisialisasi campuran mix = copy.copy(cache[i % n]) mix[0] ^= i mix = sha3_512(mix) # lakukan fnv padanya dengan banyak node cache acak berdasarkan 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) ``` Pada dasarnya, kami menggabungkan data dari 256 node cache yang dipilih secara pseudorandom, dan melakukan proses hash untuk menghitung node dataset. Seluruh dataset kemudian dihasilkan oleh: ```python def calc_dataset(full_size, cache): return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)] ``` ## Loop utama {#main-loop} Sekarang, kami menentukan loop utama yang mirip "hashimoto", di mana kami mengagregasi data dari dataset penuh untuk menghasilkan nilai akhir kami untuk header dan nonce tertentu. Dalam kode di bawah ini, `header` mewakili _hash_ SHA3-256 dari representasi RLP dari header blok yang _dipotong_, yaitu, dari header yang mengecualikan bidang **mixHash** dan **nonce**. `nonce` adalah delapan byte dari bilangan bulat tak bertanda 64 bit dalam urutan big-endian. Jadi `nonce[::-1]` adalah representasi little-endian delapan byte dari nilai tersebut: ```python def hashimoto(header, nonce, full_size, dataset_lookup): n = full_size / HASH_BYTES w = MIX_BYTES // WORD_BYTES mixhashes = MIX_BYTES / HASH_BYTES # gabungkan header+nonce menjadi seed 64 byte s = sha3_512(header + nonce[::-1]) # mulai campuran dengan s yang direplikasi mix = [] for _ in range(MIX_BYTES / HASH_BYTES): mix.extend(s) # campurkan node dataset acak 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) # kompres campuran 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]) ``` Pada dasarnya, kami mempertahankan "mix" selebar 128 byte, dan secara berulang mengambil 128 byte secara berurutan dari dataset penuh dan menggunakan fungsi `fnv` untuk menggabungkannya dengan mix tersebut. Akses berurutan 128 byte digunakan sehingga setiap putaran algoritma selalu mengambil halaman penuh dari RAM, meminimalkan kegagalan translation lookaside buffer yang secara teoritis dapat dihindari oleh ASIC. Jika output dari algoritma ini berada di bawah target yang diinginkan, maka nonce tersebut valid. Perhatikan bahwa penerapan ekstra `sha3_256` di akhir memastikan bahwa terdapat nonce perantara yang dapat diberikan untuk membuktikan bahwa setidaknya sejumlah kecil pekerjaan telah dilakukan; verifikasi PoW luar yang cepat ini dapat digunakan untuk tujuan anti-DDoS. Ini juga berfungsi untuk memberikan jaminan statistik bahwa hasilnya adalah angka 256-bit yang tidak bias. ## Penambangan {#mining} Algoritma penambangan didefinisikan sebagai berikut: ```python def mine(full_size, dataset, header, difficulty): # tambahkan padding nol pada target untuk membandingkannya dengan hash pada digit yang sama 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 ``` ## Mendefinisikan hash seed {#seed-hash} Untuk menghitung hash seed yang akan digunakan untuk menambang di atas blok tertentu, kami menggunakan algoritma berikut: ```python def get_seedhash(block): s = '\x00' * 32 for i in range(block.number // EPOCH_LENGTH): s = serialize_hash(sha3_256(s)) return s ``` Perhatikan bahwa untuk penambangan dan verifikasi yang lancar, kami menyarankan untuk menghitung sebelumnya hash seed dan dataset masa depan dalam thread terpisah. ## Bacaan lebih lanjut {#further-reading} _Tahu tentang sumber daya komunitas yang membantu Anda? Edit halaman ini dan tambahkan!_ ## Lampiran {#appendix} Kode berikut harus ditambahkan di awal jika Anda tertarik untuk menjalankan spesifikasi Python di atas sebagai kode. ```python import sha3, copy # Mengasumsikan pengurutan bit little-endian (sama seperti arsitektur 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 # fungsi hash sha3, menghasilkan 64 byte 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 ``` ### Ukuran Data {#data-sizes} Tabel pencarian berikut menyediakan sekitar 2048 Epok yang ditabulasi dari ukuran data dan ukuran cache. ```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] ```