Ethash

Ethash adalah algoritma penambangan proof-of-work Ethereum. Proof-of-work kini telah dimatikan sepenuhnya dan Ethereum sekarang diamankan menggunakan proof-of-stake sebagai gantinya. Baca lebih lanjut tentang The Merge, proof-of-stake dan mengunci. Halaman ini hanya untuk kepentingan sejarah!

Ethash adalah versi modifikasi dari algoritma Dagger-Hashimoto. Proof-of-work Ethash bersifat memory hard (opens in a new tab), yang sebelumnya dianggap membuat algoritma ini tahan terhadap ASIC. ASIC Ethash pada akhirnya dikembangkan tetapi penambangan GPU masih menjadi pilihan yang layak sampai proof-of-work dimatikan. Ethash masih digunakan untuk menambang koin lain di jaringan proof-of-work non-Ethereum lainnya.

Bagaimana cara kerja Ethash?

Sifat memory hard dicapai dengan algoritma proof-of-work yang membutuhkan pemilihan subset dari sumber daya tetap yang bergantung pada nonce dan header blok. Sumber daya ini (berukuran beberapa gigabyte) disebut DAG. DAG diubah setiap 30000 blok, sebuah jendela waktu ~125 jam yang disebut epoch (sekitar 5,2 hari) dan membutuhkan waktu untuk dihasilkan. Karena DAG hanya bergantung pada tinggi blok, ia dapat dihasilkan sebelumnya, tetapi jika tidak, klien harus 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 epoch. Perhatikan bahwa DAG tidak perlu dihasilkan untuk memverifikasi proof-of-work, yang pada dasarnya memungkinkan verifikasi dengan CPU rendah dan memori kecil.

Rute umum yang diambil oleh algoritma adalah sebagai berikut:

Terdapat sebuah seed yang dapat dihitung untuk setiap blok dengan memindai melalui header blok hingga titik tersebut.
Dari seed tersebut, seseorang dapat menghitung cache pseudorandom 16 MB. Klien ringan menyimpan cache ini.
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 linear seiring waktu.
Penambangan melibatkan pengambilan irisan acak dari dataset dan melakukan hash bersama-sama. Verifikasi dapat dilakukan dengan memori rendah dengan menggunakan cache untuk menghasilkan kembali bagian-bagian spesifik dari dataset yang Anda butuhkan, sehingga Anda hanya perlu menyimpan cache.

Dataset besar ini diperbarui setiap 30000 blok, sehingga sebagian besar upaya penambang akan dihabiskan untuk membaca dataset, bukan membuat perubahan padanya.

Definisi

Kami menggunakan definisi berikut:

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

Penggunaan 'SHA3'

Pengembangan Ethereum bertepatan dengan pengembangan standar SHA3, dan proses standar membuat perubahan terlambat pada padding dari 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 (opens in a new tab), di sini (opens in a new tab), atau di sini (opens in a new tab).

Harap diingat hal tersebut karena hash "sha3" dirujuk dalam deskripsi algoritma di bawah ini.

Parameter

Parameter untuk cache dan dataset Ethash bergantung pada nomor blok. Ukuran cache dan ukuran dataset keduanya tumbuh secara linear; namun, kami selalu mengambil bilangan prima tertinggi di bawah ambang batas yang tumbuh secara linear untuk mengurangi risiko keteraturan yang tidak disengaja yang mengarah pada perilaku siklik.

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

Sekarang, kami menentukan fungsi untuk menghasilkan cache:

def mkcache(cache_size, seed):
    n = cache_size // HASH_BYTES

    # Sequentially produce the initial dataset # Hasilkan dataset awal secara berurutan
    o = [sha3_512(seed)]
    for i in range(1, n):
        o.append(sha3_512(o[-1]))

    # Use a low-round version of randmemohash # 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 dari Sergio Demian Lerner dari Strict Memory Hard Hashing Functions (2014) (opens in a new tab). Outputnya adalah sekumpulan 524288 nilai 64-byte.

Fungsi agregasi data

Kami menggunakan algoritma yang terinspirasi oleh hash FNV (opens in a new tab) 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.

FNV_PRIME = 0x01000193

def fnv(v1, v2):
    return ((v1 * FNV_PRIME) ^ v2) % 2**32

Harap dicatat, meskipun yellow paper menentukan fnv sebagai v1*(FNV_PRIME ^ v2), semua implementasi saat ini secara konsisten menggunakan definisi di atas.

Perhitungan dataset penuh

Setiap item 64-byte dalam dataset penuh 1 GB dihitung sebagai berikut:

def calc_dataset_item(cache, i):
    n = len(cache)
    r = HASH_BYTES // WORD_BYTES
    # initialize the mix # inisialisasi campuran
    mix = copy.copy(cache[i % n])
    mix[0] ^= i
    mix = sha3_512(mix)
    # fnv it with a lot of random cache nodes based on i # terapkan 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 hash untuk menghitung node dataset. Seluruh dataset kemudian dihasilkan oleh:

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

Loop utama

Sekarang, kami menentukan loop utama yang mirip dengan "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:

def hashimoto(header, nonce, full_size, dataset_lookup):
    n = full_size / HASH_BYTES
    w = MIX_BYTES // WORD_BYTES
    mixhashes = MIX_BYTES / HASH_BYTES
    # combine header+nonce into a 64 byte seed # gabungkan header+nonce menjadi seed 64 byte
    s = sha3_512(header + nonce[::-1])
    # start the mix with replicated s # mulai campuran dengan s yang direplikasi
    mix = []
    for _ in range(MIX_BYTES / HASH_BYTES):
        mix.extend(s)
    # mix in random dataset nodes # 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)
    # compress mix # 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 "campuran" selebar 128 byte, dan berulang kali mengambil 128 byte secara berurutan dari dataset penuh dan menggunakan fungsi fnv untuk menggabungkannya dengan campuran 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

Algoritma penambangan didefinisikan sebagai berikut:

def mine(full_size, dataset, header, difficulty):
    # zero-pad target to compare with hash on the same digit # tambahkan padding nol pada target untuk dibandingkan 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

Untuk menghitung hash seed yang akan digunakan untuk menambang di atas blok tertentu, kami menggunakan algoritma berikut:

 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 merekomendasikan untuk menghitung sebelumnya hash seed dan dataset masa depan dalam thread terpisah.

Bacaan lebih lanjut

Tahu tentang sumber daya komunitas yang membantu Anda? Edit halaman ini dan tambahkan!

Lampiran

Kode berikut harus ditambahkan di awal jika Anda tertarik untuk menjalankan spesifikasi python di atas sebagai kode.

import sha3, copy

# Assumes little endian bit ordering (same as Intel architectures) # Mengasumsikan pengurutan bit little endian (sama dengan 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

# sha3 hash function, outputs 64 bytes # 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

Tabel pencarian berikut menyediakan sekitar 2048 epoch yang ditabulasi dari ukuran data dan ukuran cache.

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]