پرش به محتوای اصلی
Change page

یک الگوریتم اثبات انجام کار برای اتریوم ۱. ۰

آخرین ویرایش: @sharifi.masoud(opens in a new tab), ۱۶ اسفند ۱۴۰۲

Ethash الگوریتم استخراج اثبات کار اتریوم بود. اثبات کار اکنون **به طور کامل خاموش شده** و اتریوم اکنون با استفاده از اثبات سهام امن شده است. درباره‌ ادغام و اثبات سهام و سهام گذاری بیشتر بخوانید. این صفحه صرفاً برای علاقه‌مندان به تاریخ است!

Ethash(opens in a new tab) نسخه اصلاح شده الگوریتم Dagger-Hashimoto است. اثبات کار Ethash نیازمند حافظه سخت(opens in a new tab) است که تصور می‌شد این الگوریتم را در برابر دستگاه‌های ASIC مقاوم می‌کند. در نهایت، دستگاه‌های Ethash ASIC توسعه یافتند، اما تا زمانی که اثبات کار خاموش شد، استخراج با GPU همچنان یک گزینه قابل اجرا بود. Ethash هنوز برای استخراج سکه های دیگر در سایر شبکه های اثبات کار غیر اتریوم استفاده می شود.

Ethash چگونه کار می کند؟

سختی حافظه با الگوریتم اثبات کار به دست می آید که مستلزم انتخاب زیر مجموعه های یک منبع ثابت وابسته به سر نانس و بلوک است. این منبع (به اندازه چند گیگابایت) DAG نامیده می شود. DAG هر 30000 بلوک تغییر می کند، یعنی یک پنجره حدودا 125 ساعته به نام ایپوک (تقریباً 5.2 روز) و مدتی طول می کشد تا تولید شود. از آنجا که DAG فقط به ارتفاع بلوک بستگی دارد، می‌توان آن را از پیش تولید کرد، اما اگر تولید نشده باشد، کاربر باید تا پایان این فرآیند منتظر بماند تا بتواند بلوک تولید کند. اگر کاربرها DAGها را از قبل تولید و ذخیره نکنند، ممکن است شبکه در هر انتقال دوره با تأخیر عظیم در بلوک مواجه شود. توجه داشته باشید که برای تأیید اثبات کار نیازی به تولید DAG نیست و این امکان را می‌دهد که تأیید با پردازنده کم مصرف و حافظه کم انجام شود.

مسیر کلی که الگوریتم طی می کند به شرح زیر است:

  1. برای هر بلوک یک بذر وجود دارد که با اسکن کردن سرهای بلوک تا آن نقطه قابل محاسبه است.
  2. از روی این بذر، می‌توان یک حافظه پنهان شبه‌تصادفی ۱۶ مگابایتی محاسبه کرد. کاربرهای سبک، حافظه پنهان را ذخیره می‌کنند.
  3. از حافظه پنهان، می‌توانیم یک مجموعه داده یک گیگابایتی تولید کنیم، طوری که هر آیتم در این مجموعه داده فقط به تعداد کمی از آیتم‌های حافظه پنهان وابسته است. کاربرهای کامل و استخراجگرها مجموعه داده را ذخیره می‌کنند. مجموعه داده به صورت خطی با زمان رشد می کند.
  4. استخراج شامل گرفتن برش‌های تصادفی از مجموعه داده و هش کردن آن‌ها با هم است. تأیید را می‌توان با استفاده از حافظه پنهان برای بازسازی قطعات خاص مجموعه داده مورد نیاز با حافظه کم انجام داد، بنابراین فقط نیاز به ذخیره حافظه پنهان دارید.

مجموعه داده بزرگ هر 30000 بلوک یک بار به‌روزرسانی می‌شود، بنابراین اکثر تلاش‌های یک استخراجگر صرف خواندن مجموعه داده می‌شود، نه ایجاد تغییر در آن.

تعاریف

ما از تعاریف زیر استفاده می کنیم:

1WORD_BYTES = 4 # bytes in word
2DATASET_BYTES_INIT = 2**30 # bytes in dataset at genesis
3DATASET_BYTES_GROWTH = 2**23 # dataset growth per epoch
4CACHE_BYTES_INIT = 2**24 # bytes in cache at genesis
5CACHE_BYTES_GROWTH = 2**17 # cache growth per epoch
6CACHE_MULTIPLIER=1024 # Size of the DAG relative to the cache
7EPOCH_LENGTH = 30000 # blocks per epoch
8MIX_BYTES = 128 # width of mix
9HASH_BYTES = 64 # hash length in bytes
10DATASET_PARENTS = 256 # number of parents of each dataset element
11CACHE_ROUNDS = 3 # number of rounds in cache production
12ACCESSES = 64 # number of accesses in hashimoto loop
نمایش همه

استفاده از 'SHA3'

توسعه اتریوم همزمان با توسعه استاندارد SHA3 انجام شد و فرآیند استانداردسازی تغییری دیرهنگام در پرکردن الگوریتم هش نهایی ایجاد کرد، طوری که هش‌های "sha3_256" و "sha3_512" اتریوم هش‌های استاندارد sha3 نیستند، بلکه نوعی متفاوت هستند که اغلب در زمینه‌های دیگر به عنوان "Keccak-256" و "Keccak-512" شناخته می‌شوند. برای اطلاعات بیشتر، به بحث‌های انجام شده در اینجا(opens in a new tab)، اینجا(opens in a new tab)، یا اینجا(opens in a new tab) مراجعه کنید.

لطفا این نکته را در نظر داشته باشید که در توضیحات الگوریتم زیر به هش‌های "sha3" اشاره شده است.

پارامترها

پارامترهای حافظه پنهان و مجموعه داده Ethash وابسته به شماره بلوک هستند. اندازه حافظه پنهان و اندازه مجموعه داده هر دو به صورت خطی رشد می‌کنند؛ با این حال، برای کاهش خطر ایجاد الگوهای تکراری منجر به رفتار چرخه‌ای، همیشه بزرگترین عدد اول کمتر از آستانه رشد خطی را انتخاب می‌کنیم.

1def get_cache_size(block_number):
2 sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
3 sz -= HASH_BYTES
4 while not isprime(sz / HASH_BYTES):
5 sz -= 2 * HASH_BYTES
6 return sz
7
8def get_full_size(block_number):
9 sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
10 sz -= MIX_BYTES
11 while not isprime(sz / MIX_BYTES):
12 sz -= 2 * MIX_BYTES
13 return sz
نمایش همه
کپی

جدول‌های مقادیر اندازه حافظه پنهان و مجموعه داده در ضمیمه ارائه شده است.

تولید حافظه پنهان

اکنون تابع تولید حافظه پنهان را مشخص می کنیم:

1def mkcache(cache_size, seed):
2 n = cache_size // HASH_BYTES
3
4 # Sequentially produce the initial dataset
5 o = [sha3_512(seed)]
6 for i in range(1, n):
7 o.append(sha3_512(o[-1]))
8
9 # Use a low-round version of randmemohash
10 for _ in range(CACHE_ROUNDS):
11 for i in range(n):
12 v = o[i][0] % n
13 o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))
14
15 return o
نمایش همه
کپی

فرآیند تولید حافظه پنهان شامل پر کردن متوالی 32 مگابایت حافظه میشود، سپس دو پاس از الگوریتم RandMemoHash سرجیو دمیان لرنر از Strict Memory Hard Hashing Functions (2014) انجام می‌شود(opens in a new tab). خروجی، یک مجموعه شامل ۵۲۴۲۸۸ مقدار ۶۴ بایتی است.

تابع تجمیع داده ها

در برخی موارد از یک الگوریتم الهام گرفته از هش FNV(opens in a new tab) به عنوان جایگزینی غیر تداعی برای XOR استفاده می‌کنیم. توجه داشته باشید که ما عدد اول را در کل ورودی ۳۲ بیتی ضرب می‌کنیم، برخلاف مشخصات FNV-1 که عدد اول را با هر بایت (octet) به نوبت ضرب می‌کند.

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

لطفا توجه داشته باشید که حتی وایت‌پیپر نیز fnv را به عنوان v1*(FNV_PRIME ^ v2) مشخص می‌کند، اما تمام اجراهای فعلی به طور مداوم از تعریف بالا استفاده می‌کنند.

محاسبه کامل مجموعه داده

هر آیتم ۶۴ بایتی در کل مجموعه داده ۱ گیگابایتی به شرح زیر محاسبه می‌شود:

1def calc_dataset_item(cache, i):
2 n = len(cache)
3 r = HASH_BYTES // WORD_BYTES
4 # initialize the mix
5 mix = copy.copy(cache[i % n])
6 mix[0] ^= i
7 mix = sha3_512(mix)
8 # fnv it with a lot of random cache nodes based on i
9 for j in range(DATASET_PARENTS):
10 cache_index = fnv(i ^ j, mix[j % r])
11 mix = map(fnv, mix, cache[cache_index % n])
12 return sha3_512(mix)
نمایش همه
کپی

در اصل، ما داده‌ها را از ۲۵۶ گره حافظه پنهان انتخاب شده به صورت شبه‌تصادفی ترکیب می‌کنیم و آن را هش می‌کنیم تا گره مجموعه داده را محاسبه کنیم. کل مجموعه داده سپس با استفاده از روش زیر تولید می‌شود:

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

حلقه اصلی

حالا حلقه اصلی شبیه به "hashimoto" را مشخص می‌کنیم که در آن داده‌ها را از کل مجموعه داده جمع‌آوری می‌کنیم تا مقدار نهایی خود را برای یک سر و نانسِ خاص تولید کنیم. در کد زیر، header نشان دهنده هش SHA3-256 از نمایش RLP یک سر بلوک بریده شده است، یعنی سر بدون فیلدهای mixHash و nonce. نانس هشت بایت از یک عدد صحیح بدون علامت ۶۴ بیتی با ترتیب بزرگ به کوچک است. پس nonce[::-1] نمایش هشت بایتی با ترتیب کوچک به بزرگ little-endian از آن مقدار است:

1def hashimoto(header, nonce, full_size, dataset_lookup):
2 n = full_size / HASH_BYTES
3 w = MIX_BYTES // WORD_BYTES
4 mixhashes = MIX_BYTES / HASH_BYTES
5 # combine header+nonce into a 64 byte seed
6 s = sha3_512(header + nonce[::-1])
7 # start the mix with replicated s
8 mix = []
9 for _ in range(MIX_BYTES / HASH_BYTES):
10 mix.extend(s)
11 # mix in random dataset nodes
12 for i in range(ACCESSES):
13 p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
14 newdata = []
15 for j in range(MIX_BYTES / HASH_BYTES):
16 newdata.extend(dataset_lookup(p + j))
17 mix = map(fnv, mix, newdata)
18 # compress mix
19 cmix = []
20 for i in range(0, len(mix), 4):
21 cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))
22 return {
23 "mix digest": serialize_hash(cmix),
24 "result": serialize_hash(sha3_256(s+cmix))
25 }
26
27def hashimoto_light(full_size, cache, header, nonce):
28 return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))
29
30def hashimoto_full(full_size, dataset, header, nonce):
31 return hashimoto(header, nonce, full_size, lambda x: dataset[x])
نمایش همه
کپی

در اصل، ما یک "میکس" ۱۲۸ بایتی را حفظ می‌کنیم و به طور متوالی ۱۲۸ بایت را از کل مجموعه داده دریافت کرده و از تابع fnv برای ترکیب آن با میکس استفاده می‌کنیم. از ۱۲۸ بایت دسترسی متوالی استفاده می‌شود تا هر دور از الگوریتم همیشه یک صفحه کامل را از رم دریافت کند و خطای حافظه پنهان ترجمه را به حداقل برساند که از نظر تئوری ASICها می‌توانند از آن جلوگیری کنند.

اگر خروجی این الگوریتم کمتر از هدف مورد نظر باشد، پس نانس معتبر است. توجه داشته باشید که اعمال اضافی sha3_256 در انتها تضمین می‌کند که یک نانس میانی وجود دارد که می‌تواند برای اثبات انجام حداقل مقدار کار ارائه شود؛ این تأیید سریع PoW خارجی می‌تواند برای اهداف ضد DDoS استفاده شود. همچنین برای ارائه اطمینان آماری از اینکه نتیجه یک عدد ۲۵۶ بیتی بدون سوگیری است، عمل می‌کند.

استخراج

الگوریتم استخراج به صورت زیر تعریف شده است:

1def mine(full_size, dataset, header, difficulty):
2 # zero-pad target to compare with hash on the same digit
3 target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
4 from random import randint
5 nonce = randint(0, 2**64)
6 while hashimoto_full(full_size, dataset, header, nonce) > target:
7 nonce = (nonce + 1) % 2**64
8 return nonce
کپی

تعریف هش بذر

برای محاسبه هش بذر که برای استخراج در بالای یک بلوک مورد استفاده قرار می گیرد، از الگوریتم زیر استفاده می کنیم:

1 def get_seedhash(block):
2 s = '\x00' * 32
3 for i in range(block.number // EPOCH_LENGTH):
4 s = serialize_hash(sha3_256(s))
5 return s
کپی

توجه داشته باشید که برای استخراج و تأیید روان، توصیه می‌شود که seedhashها و مجموعه داده‌های آینده را در یک رشته جداگانه از قبل محاسبه کنید.

بیشتر بخوانید

آیا می‌خواهید در مورد منابع جامعه که به شما کمک کرده بدانید؟ این صفحه را ویرایش کنید و آن را اضافه کنید!

پیوست‌

در صورتی که علاقه‌مند به اجرای مشخصات پایتون بالا به عنوان کد هستید، باید کد زیر را در ابتدای آن قرار دهید.

1import sha3, copy
2
3# Assumes little endian bit ordering (same as Intel architectures)
4def decode_int(s):
5 return int(s[::-1].encode('hex'), 16) if s else 0
6
7def encode_int(s):
8 a = "%x" % s
9 return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]
10
11def zpad(s, length):
12 return s + '\x00' * max(0, length - len(s))
13
14def serialize_hash(h):
15 return ''.join([zpad(encode_int(x), 4) for x in h])
16
17def deserialize_hash(h):
18 return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
19
20def hash_words(h, sz, x):
21 if isinstance(x, list):
22 x = serialize_hash(x)
23 y = h(x)
24 return deserialize_hash(y)
25
26def serialize_cache(ds):
27 return ''.join([serialize_hash(h) for h in ds])
28
29serialize_dataset = serialize_cache
30
31# sha3 hash function, outputs 64 bytes
32def sha3_512(x):
33 return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)
34
35def sha3_256(x):
36 return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)
37
38def xor(a, b):
39 return a ^ b
40
41def isprime(x):
42 for i in range(2, int(x**0.5)):
43 if x % i == 0:
44 return False
45 return True
نمایش همه
کپی

اندازه داده ها

جدول‌های جستجوی زیر تقریباً ۲۰۴۸ دوره محاسباتی جدول‌بندی شده از اندازه‌های داده‌ها و اندازه‌های کش را ارائه می‌دهند.

1def get_datasize(block_number):
2 return data_sizes[block_number // EPOCH_LENGTH]
3
4def get_cachesize(block_number):
5 return cache_sizes[block_number // EPOCH_LENGTH]
6
7data_sizes = [
81073739904, 1082130304, 1090514816, 1098906752, 1107293056,
91115684224, 1124070016, 1132461952, 1140849536, 1149232768,
101157627776, 1166013824, 1174404736, 1182786944, 1191180416,
111199568512, 1207958912, 1216345216, 1224732032, 1233124736,
121241513344, 1249902464, 1258290304, 1266673792, 1275067264,
131283453312, 1291844992, 1300234112, 1308619904, 1317010048,
141325397376, 1333787776, 1342176128, 1350561664, 1358954368,
151367339392, 1375731584, 1384118144, 1392507008, 1400897408,
161409284736, 1417673344, 1426062464, 1434451072, 1442839168,
171451229056, 1459615616, 1468006016, 1476394112, 1484782976,
181493171584, 1501559168, 1509948032, 1518337664, 1526726528,
191535114624, 1543503488, 1551892096, 1560278656, 1568669056,
201577056384, 1585446272, 1593831296, 1602219392, 1610610304,
211619000192, 1627386752, 1635773824, 1644164224, 1652555648,
221660943488, 1669332608, 1677721216, 1686109312, 1694497664,
231702886272, 1711274624, 1719661184, 1728047744, 1736434816,
241744829056, 1753218944, 1761606272, 1769995904, 1778382464,
251786772864, 1795157888, 1803550592, 1811937664, 1820327552,
261828711552, 1837102976, 1845488768, 1853879936, 1862269312,
271870656896, 1879048064, 1887431552, 1895825024, 1904212096,
281912601216, 1920988544, 1929379456, 1937765504, 1946156672,
291954543232, 1962932096, 1971321728, 1979707264, 1988093056,
301996487552, 2004874624, 2013262208, 2021653888, 2030039936,
312038430848, 2046819968, 2055208576, 2063596672, 2071981952,
322080373632, 2088762752, 2097149056, 2105539712, 2113928576,
332122315136, 2130700672, 2139092608, 2147483264, 2155872128,
342164257664, 2172642176, 2181035392, 2189426048, 2197814912,
352206203008, 2214587264, 2222979712, 2231367808, 2239758208,
362248145024, 2256527744, 2264922752, 2273312128, 2281701248,
372290086272, 2298476672, 2306867072, 2315251072, 2323639168,
382332032128, 2340420224, 2348808064, 2357196416, 2365580416,
392373966976, 2382363008, 2390748544, 2399139968, 2407530368,
402415918976, 2424307328, 2432695424, 2441084288, 2449472384,
412457861248, 2466247808, 2474637184, 2483026816, 2491414144,
422499803776, 2508191872, 2516582272, 2524970368, 2533359232,
432541743488, 2550134144, 2558525056, 2566913408, 2575301504,
442583686528, 2592073856, 2600467328, 2608856192, 2617240448,
452625631616, 2634022016, 2642407552, 2650796416, 2659188352,
462667574912, 2675965312, 2684352896, 2692738688, 2701130624,
472709518464, 2717907328, 2726293376, 2734685056, 2743073152,
482751462016, 2759851648, 2768232832, 2776625536, 2785017728,
492793401984, 2801794432, 2810182016, 2818571648, 2826959488,
502835349376, 2843734144, 2852121472, 2860514432, 2868900992,
512877286784, 2885676928, 2894069632, 2902451584, 2910843008,
522919234688, 2927622784, 2936011648, 2944400768, 2952789376,
532961177728, 2969565568, 2977951616, 2986338944, 2994731392,
543003120256, 3011508352, 3019895936, 3028287104, 3036675968,
553045063808, 3053452928, 3061837696, 3070228352, 3078615424,
563087003776, 3095394944, 3103782272, 3112173184, 3120562048,
573128944768, 3137339264, 3145725056, 3154109312, 3162505088,
583170893184, 3179280256, 3187669376, 3196056704, 3204445568,
593212836736, 3221224064, 3229612928, 3238002304, 3246391168,
603254778496, 3263165824, 3271556224, 3279944576, 3288332416,
613296719232, 3305110912, 3313500032, 3321887104, 3330273152,
623338658944, 3347053184, 3355440512, 3363827072, 3372220288,
633380608384, 3388997504, 3397384576, 3405774208, 3414163072,
643422551936, 3430937984, 3439328384, 3447714176, 3456104576,
653464493952, 3472883584, 3481268864, 3489655168, 3498048896,
663506434432, 3514826368, 3523213952, 3531603584, 3539987072,
673548380288, 3556763264, 3565157248, 3573545344, 3581934464,
683590324096, 3598712704, 3607098752, 3615488384, 3623877248,
693632265856, 3640646528, 3649043584, 3657430144, 3665821568,
703674207872, 3682597504, 3690984832, 3699367808, 3707764352,
713716152448, 3724541056, 3732925568, 3741318016, 3749706368,
723758091136, 3766481536, 3774872704, 3783260032, 3791650432,
733800036224, 3808427648, 3816815488, 3825204608, 3833592704,
743841981568, 3850370432, 3858755968, 3867147904, 3875536256,
753883920512, 3892313728, 3900702592, 3909087872, 3917478784,
763925868416, 3934256512, 3942645376, 3951032192, 3959422336,
773967809152, 3976200064, 3984588416, 3992974976, 4001363584,
784009751168, 4018141312, 4026530432, 4034911616, 4043308928,
794051695488, 4060084352, 4068472448, 4076862848, 4085249408,
804093640576, 4102028416, 4110413696, 4118805632, 4127194496,
814135583104, 4143971968, 4152360832, 4160746112, 4169135744,
824177525888, 4185912704, 4194303616, 4202691968, 4211076736,
834219463552, 4227855488, 4236246656, 4244633728, 4253022848,
844261412224, 4269799808, 4278184832, 4286578048, 4294962304,
854303349632, 4311743104, 4320130432, 4328521088, 4336909184,
864345295488, 4353687424, 4362073472, 4370458496, 4378852736,
874387238528, 4395630208, 4404019072, 4412407424, 4420790656,
884429182848, 4437571456, 4445962112, 4454344064, 4462738048,
894471119232, 4479516544, 4487904128, 4496289664, 4504682368,
904513068416, 4521459584, 4529846144, 4538232704, 4546619776,
914555010176, 4563402112, 4571790208, 4580174464, 4588567936,
924596957056, 4605344896, 4613734016, 4622119808, 4630511488,
934638898816, 4647287936, 4655675264, 4664065664, 4672451968,
944680842624, 4689231488, 4697620352, 4706007424, 4714397056,
954722786176, 4731173248, 4739562368, 4747951744, 4756340608,
964764727936, 4773114496, 4781504384, 4789894784, 4798283648,
974806667648, 4815059584, 4823449472, 4831835776, 4840226176,
984848612224, 4857003392, 4865391488, 4873780096, 4882169728,
994890557312, 4898946944, 4907333248, 4915722368, 4924110976,
1004932499328, 4940889728, 4949276032, 4957666432, 4966054784,
1014974438016, 4982831488, 4991221376, 4999607168, 5007998848,
1025016386432, 5024763776, 5033164672, 5041544576, 5049941888,
1035058329728, 5066717056, 5075107456, 5083494272, 5091883904,
1045100273536, 5108662144, 5117048192, 5125436032, 5133827456,
1055142215296, 5150605184, 5158993024, 5167382144, 5175769472,
1065184157568, 5192543872, 5200936064, 5209324928, 5217711232,
1075226102656, 5234490496, 5242877312, 5251263872, 5259654016,
1085268040832, 5276434304, 5284819328, 5293209728, 5301598592,
1095309986688, 5318374784, 5326764416, 5335151488, 5343542144,
1105351929472, 5360319872, 5368706944, 5377096576, 5385484928,
1115393871232, 5402263424, 5410650496, 5419040384, 5427426944,
1125435816576, 5444205952, 5452594816, 5460981376, 5469367936,
1135477760896, 5486148736, 5494536832, 5502925952, 5511315328,
1145519703424, 5528089984, 5536481152, 5544869504, 5553256064,
1155561645696, 5570032768, 5578423936, 5586811264, 5595193216,
1165603585408, 5611972736, 5620366208, 5628750464, 5637143936,
1175645528192, 5653921408, 5662310272, 5670694784, 5679082624,
1185687474048, 5695864448, 5704251008, 5712641408, 5721030272,
1195729416832, 5737806208, 5746194304, 5754583936, 5762969984,
1205771358592, 5779748224, 5788137856, 5796527488, 5804911232,
1215813300608, 5821692544, 5830082176, 5838468992, 5846855552,
1225855247488, 5863636096, 5872024448, 5880411008, 5888799872,
1235897186432, 5905576832, 5913966976, 5922352768, 5930744704,
1245939132288, 5947522432, 5955911296, 5964299392, 5972688256,
1255981074304, 5989465472, 5997851008, 6006241408, 6014627968,
1266023015552, 6031408256, 6039796096, 6048185216, 6056574848,
1276064963456, 6073351808, 6081736064, 6090128768, 6098517632,
1286106906496, 6115289216, 6123680896, 6132070016, 6140459648,
1296148849024, 6157237376, 6165624704, 6174009728, 6182403712,
1306190792064, 6199176064, 6207569792, 6215952256, 6224345216,
1316232732544, 6241124224, 6249510272, 6257899136, 6266287744,
1326274676864, 6283065728, 6291454336, 6299843456, 6308232064,
1336316620928, 6325006208, 6333395584, 6341784704, 6350174848,
1346358562176, 6366951296, 6375337856, 6383729536, 6392119168,
1356400504192, 6408895616, 6417283456, 6425673344, 6434059136,
1366442444672, 6450837376, 6459223424, 6467613056, 6476004224,
1376484393088, 6492781952, 6501170048, 6509555072, 6517947008,
1386526336384, 6534725504, 6543112832, 6551500672, 6559888768,
1396568278656, 6576662912, 6585055616, 6593443456, 6601834112,
1406610219648, 6618610304, 6626999168, 6635385472, 6643777408,
1416652164224, 6660552832, 6668941952, 6677330048, 6685719424,
1426694107776, 6702493568, 6710882176, 6719274112, 6727662976,
1436736052096, 6744437632, 6752825984, 6761213824, 6769604224,
1446777993856, 6786383488, 6794770816, 6803158144, 6811549312,
1456819937664, 6828326528, 6836706176, 6845101696, 6853491328,
1466861880448, 6870269312, 6878655104, 6887046272, 6895433344,
1476903822208, 6912212864, 6920596864, 6928988288, 6937377152,
1486945764992, 6954149248, 6962544256, 6970928768, 6979317376,
1496987709312, 6996093824, 7004487296, 7012875392, 7021258624,
1507029652352, 7038038912, 7046427776, 7054818944, 7063207808,
1517071595136, 7079980928, 7088372608, 7096759424, 7105149824,
1527113536896, 7121928064, 7130315392, 7138699648, 7147092352,
1537155479168, 7163865728, 7172249984, 7180648064, 7189036672,
1547197424768, 7205810816, 7214196608, 7222589824, 7230975104,
1557239367552, 7247755904, 7256145536, 7264533376, 7272921472,
1567281308032, 7289694848, 7298088832, 7306471808, 7314864512,
1577323253888, 7331643008, 7340029568, 7348419712, 7356808832,
1587365196672, 7373585792, 7381973888, 7390362752, 7398750592,
1597407138944, 7415528576, 7423915648, 7432302208, 7440690304,
1607449080192, 7457472128, 7465860992, 7474249088, 7482635648,
1617491023744, 7499412608, 7507803008, 7516192384, 7524579968,
1627532967296, 7541358464, 7549745792, 7558134656, 7566524032,
1637574912896, 7583300992, 7591690112, 7600075136, 7608466816,
1647616854912, 7625244544, 7633629824, 7642020992, 7650410368,
1657658794112, 7667187328, 7675574912, 7683961984, 7692349568,
1667700739712, 7709130368, 7717519232, 7725905536, 7734295424,
1677742683264, 7751069056, 7759457408, 7767849088, 7776238208,
1687784626816, 7793014912, 7801405312, 7809792128, 7818179968,
1697826571136, 7834957184, 7843347328, 7851732352, 7860124544,
1707868512384, 7876902016, 7885287808, 7893679744, 7902067072,
1717910455936, 7918844288, 7927230848, 7935622784, 7944009344,
1727952400256, 7960786048, 7969176704, 7977565312, 7985953408,
1737994339968, 8002730368, 8011119488, 8019508096, 8027896192,
1748036285056, 8044674688, 8053062272, 8061448832, 8069838464,
1758078227328, 8086616704, 8095006592, 8103393664, 8111783552,
1768120171392, 8128560256, 8136949376, 8145336704, 8153726848,
1778162114944, 8170503296, 8178891904, 8187280768, 8195669632,
1788204058496, 8212444544, 8220834176, 8229222272, 8237612672,
1798246000768, 8254389376, 8262775168, 8271167104, 8279553664,
1808287944064, 8296333184, 8304715136, 8313108352, 8321497984,
1818329885568, 8338274432, 8346663296, 8355052928, 8363441536,
1828371828352, 8380217984, 8388606592, 8396996224, 8405384576,
1838413772672, 8422161536, 8430549376, 8438939008, 8447326592,
1848455715456, 8464104832, 8472492928, 8480882048, 8489270656,
1858497659776, 8506045312, 8514434944, 8522823808, 8531208832,
1868539602304, 8547990656, 8556378752, 8564768384, 8573154176,
1878581542784, 8589933952, 8598322816, 8606705024, 8615099264,
1888623487872, 8631876992, 8640264064, 8648653952, 8657040256,
1898665430656, 8673820544, 8682209152, 8690592128, 8698977152,
1908707374464, 8715763328, 8724151424, 8732540032, 8740928384,
1918749315712, 8757704576, 8766089344, 8774480768, 8782871936,
1928791260032, 8799645824, 8808034432, 8816426368, 8824812928,
1938833199488, 8841591424, 8849976448, 8858366336, 8866757248,
1948875147136, 8883532928, 8891923328, 8900306816, 8908700288,
1958917088384, 8925478784, 8933867392, 8942250368, 8950644608,
1968959032704, 8967420544, 8975809664, 8984197504, 8992584064,
1979000976256, 9009362048, 9017752448, 9026141312, 9034530688,
1989042917504, 9051307904, 9059694208, 9068084864, 9076471424,
1999084861824, 9093250688, 9101638528, 9110027648, 9118416512,
2009126803584, 9135188096, 9143581312, 9151969664, 9160356224,
2019168747136, 9177134464, 9185525632, 9193910144, 9202302848,
2029210690688, 9219079552, 9227465344, 9235854464, 9244244864,
2039252633472, 9261021824, 9269411456, 9277799296, 9286188928,
2049294574208, 9302965888, 9311351936, 9319740032, 9328131968,
2059336516736, 9344907392, 9353296768, 9361685888, 9370074752,
2069378463616, 9386849408, 9395239808, 9403629184, 9412016512,
2079420405376, 9428795008, 9437181568, 9445570688, 9453960832,
2089462346624, 9470738048, 9479121536, 9487515008, 9495903616,
2099504289664, 9512678528, 9521067904, 9529456256, 9537843584,
2109546233728, 9554621312, 9563011456, 9571398784, 9579788672,
2119588178304, 9596567168, 9604954496, 9613343104, 9621732992,
2129630121856, 9638508416, 9646898816, 9655283584, 9663675776,
2139672061312, 9680449664, 9688840064, 9697230464, 9705617536,
2149714003584, 9722393984, 9730772608, 9739172224, 9747561088,
2159755945344, 9764338816, 9772726144, 9781116544, 9789503872,
2169797892992, 9806282624, 9814670464, 9823056512, 9831439232,
2179839833984, 9848224384, 9856613504, 9865000576, 9873391232,
2189881772416, 9890162816, 9898556288, 9906940544, 9915333248,
2199923721088, 9932108672, 9940496512, 9948888448, 9957276544,
2209965666176, 9974048384, 9982441088, 9990830464, 9999219584,
22110007602816, 10015996544, 10024385152, 10032774016, 10041163648,
22210049548928, 10057940096, 10066329472, 10074717824, 10083105152,
22310091495296, 10099878784, 10108272256, 10116660608, 10125049216,
22410133437312, 10141825664, 10150213504, 10158601088, 10166991232,
22510175378816, 10183766144, 10192157312, 10200545408, 10208935552,
22610217322112, 10225712768, 10234099328, 10242489472, 10250876032,
22710259264896, 10267656064, 10276042624, 10284429184, 10292820352,
22810301209472, 10309598848, 10317987712, 10326375296, 10334763392,
22910343153536, 10351541632, 10359930752, 10368318592, 10376707456,
23010385096576, 10393484672, 10401867136, 10410262144, 10418647424,
23110427039104, 10435425664, 10443810176, 10452203648, 10460589952,
23210468982144, 10477369472, 10485759104, 10494147712, 10502533504,
23310510923392, 10519313536, 10527702656, 10536091264, 10544478592,
23410552867712, 10561255808, 10569642368, 10578032768, 10586423168,
23510594805632, 10603200128, 10611588992, 10619976064, 10628361344,
23610636754048, 10645143424, 10653531776, 10661920384, 10670307968,
23710678696832, 10687086464, 10695475072, 10703863168, 10712246144,
23810720639616, 10729026688, 10737414784, 10745806208, 10754190976,
23910762581376, 10770971264, 10779356288, 10787747456, 10796135552,
24010804525184, 10812915584, 10821301888, 10829692288, 10838078336,
24110846469248, 10854858368, 10863247232, 10871631488, 10880023424,
24210888412032, 10896799616, 10905188992, 10913574016, 10921964672,
24310930352768, 10938742912, 10947132544, 10955518592, 10963909504,
24410972298368, 10980687488, 10989074816, 10997462912, 11005851776,
24511014241152, 11022627712, 11031017344, 11039403904, 11047793024,
24611056184704, 11064570752, 11072960896, 11081343872, 11089737856,
24711098128256, 11106514816, 11114904448, 11123293568, 11131680128,
24811140065152, 11148458368, 11156845696, 11165236864, 11173624192,
24911182013824, 11190402688, 11198790784, 11207179136, 11215568768,
25011223957376, 11232345728, 11240734592, 11249122688, 11257511296,
25111265899648, 11274285952, 11282675584, 11291065472, 11299452544,
25211307842432, 11316231296, 11324616832, 11333009024, 11341395584,
25311349782656, 11358172288, 11366560384, 11374950016, 11383339648,
25411391721856, 11400117376, 11408504192, 11416893568, 11425283456,
25511433671552, 11442061184, 11450444672, 11458837888, 11467226752,
25611475611776, 11484003968, 11492392064, 11500780672, 11509169024,
25711517550976, 11525944448, 11534335616, 11542724224, 11551111808,
25811559500672, 11567890304, 11576277376, 11584667008, 11593056128,
25911601443456, 11609830016, 11618221952, 11626607488, 11634995072,
26011643387776, 11651775104, 11660161664, 11668552576, 11676940928,
26111685330304, 11693718656, 11702106496, 11710496128, 11718882688,
26211727273088, 11735660416, 11744050048, 11752437376, 11760824704,
26311769216128, 11777604736, 11785991296, 11794381952, 11802770048,
26411811157888, 11819548544, 11827932544, 11836324736, 11844713344,
26511853100928, 11861486464, 11869879936, 11878268032, 11886656896,
26611895044992, 11903433088, 11911822976, 11920210816, 11928600448,
26711936987264, 11945375872, 11953761152, 11962151296, 11970543488,
26811978928512, 11987320448, 11995708288, 12004095104, 12012486272,
26912020875136, 12029255552, 12037652096, 12046039168, 12054429568,
27012062813824, 12071206528, 12079594624, 12087983744, 12096371072,
27112104759936, 12113147264, 12121534592, 12129924992, 12138314624,
27212146703232, 12155091584, 12163481216, 12171864704, 12180255872,
27312188643968, 12197034112, 12205424512, 12213811328, 12222199424,
27412230590336, 12238977664, 12247365248, 12255755392, 12264143488,
27512272531584, 12280920448, 12289309568, 12297694592, 12306086528,
27612314475392, 12322865024, 12331253632, 12339640448, 12348029312,
27712356418944, 12364805248, 12373196672, 12381580928, 12389969024,
27812398357632, 12406750592, 12415138432, 12423527552, 12431916416,
27912440304512, 12448692352, 12457081216, 12465467776, 12473859968,
28012482245504, 12490636672, 12499025536, 12507411584, 12515801728,
28112524190592, 12532577152, 12540966272, 12549354368, 12557743232,
28212566129536, 12574523264, 12582911872, 12591299456, 12599688064,
28312608074624, 12616463488, 12624845696, 12633239936, 12641631616,
28412650019968, 12658407296, 12666795136, 12675183232, 12683574656,
28512691960192, 12700350592, 12708740224, 12717128576, 12725515904,
28612733906816, 12742295168, 12750680192, 12759071872, 12767460736,
28712775848832, 12784236928, 12792626816, 12801014656, 12809404288,
28812817789312, 12826181504, 12834568832, 12842954624, 12851345792,
28912859732352, 12868122496, 12876512128, 12884901248, 12893289088,
29012901672832, 12910067584, 12918455168, 12926842496, 12935232896,
29112943620736, 12952009856, 12960396928, 12968786816, 12977176192,
29212985563776, 12993951104, 13002341504, 13010730368, 13019115392,
29313027506304, 13035895168, 13044272512, 13052673152, 13061062528,
29413069446272, 13077838976, 13086227072, 13094613632, 13103000192,
29513111393664, 13119782528, 13128157568, 13136559232, 13144945024,
29613153329536, 13161724288, 13170111872, 13178502784, 13186884736,
29713195279744, 13203667072, 13212057472, 13220445824, 13228832128,
29813237221248, 13245610624, 13254000512, 13262388352, 13270777472,
29913279166336, 13287553408, 13295943296, 13304331904, 13312719488,
30013321108096, 13329494656, 13337885824, 13346274944, 13354663808,
30113363051136, 13371439232, 13379825024, 13388210816, 13396605056,
30213404995456, 13413380224, 13421771392, 13430159744, 13438546048,
30313446937216, 13455326848, 13463708288, 13472103808, 13480492672,
30413488875648, 13497269888, 13505657728, 13514045312, 13522435712,
30513530824576, 13539210112, 13547599232, 13555989376, 13564379008,
30613572766336, 13581154432, 13589544832, 13597932928, 13606320512,
30713614710656, 13623097472, 13631477632, 13639874944, 13648264064,
30813656652928, 13665041792, 13673430656, 13681818496, 13690207616,
30913698595712, 13706982272, 13715373184, 13723762048, 13732150144,
31013740536704, 13748926592, 13757316224, 13765700992, 13774090112,
31113782477952, 13790869376, 13799259008, 13807647872, 13816036736,
31213824425344, 13832814208, 13841202304, 13849591424, 13857978752,
31313866368896, 13874754688, 13883145344, 13891533184, 13899919232,
31413908311168, 13916692096, 13925085056, 13933473152, 13941866368,
31513950253696, 13958643584, 13967032192, 13975417216, 13983807616,
31613992197504, 14000582272, 14008973696, 14017363072, 14025752192,
31714034137984, 14042528384, 14050918016, 14059301504, 14067691648,
31814076083584, 14084470144, 14092852352, 14101249664, 14109635968,
31914118024832, 14126407552, 14134804352, 14143188608, 14151577984,
32014159968384, 14168357248, 14176741504, 14185127296, 14193521024,
32114201911424, 14210301824, 14218685056, 14227067264, 14235467392,
32214243855488, 14252243072, 14260630144, 14269021568, 14277409408,
32314285799296, 14294187904, 14302571392, 14310961792, 14319353728,
32414327738752, 14336130944, 14344518784, 14352906368, 14361296512,
32514369685376, 14378071424, 14386462592, 14394848128, 14403230848,
32614411627392, 14420013952, 14428402304, 14436793472, 14445181568,
32714453569664, 14461959808, 14470347904, 14478737024, 14487122816,
32814495511424, 14503901824, 14512291712, 14520677504, 14529064832,
32914537456768, 14545845632, 14554234496, 14562618496, 14571011456,
33014579398784, 14587789184, 14596172672, 14604564608, 14612953984,
33114621341312, 14629724288, 14638120832, 14646503296, 14654897536,
33214663284864, 14671675264, 14680061056, 14688447616, 14696835968,
33314705228416, 14713616768, 14722003328, 14730392192, 14738784128,
33414747172736, 14755561088, 14763947648, 14772336512, 14780725376,
33514789110144, 14797499776, 14805892736, 14814276992, 14822670208,
33614831056256, 14839444352, 14847836032, 14856222848, 14864612992,
33714872997504, 14881388672, 14889775744, 14898165376, 14906553472,
33814914944896, 14923329664, 14931721856, 14940109696, 14948497024,
33914956887424, 14965276544, 14973663616, 14982053248, 14990439808,
34014998830976, 15007216768, 15015605888, 15023995264, 15032385152,
34115040768384, 15049154944, 15057549184, 15065939072, 15074328448,
34215082715008, 15091104128, 15099493504, 15107879296, 15116269184,
34315124659584, 15133042304, 15141431936, 15149824384, 15158214272,
34415166602368, 15174991232, 15183378304, 15191760512, 15200154496,
34515208542592, 15216931712, 15225323392, 15233708416, 15242098048,
34615250489216, 15258875264, 15267265408, 15275654528, 15284043136,
34715292431488, 15300819584, 15309208192, 15317596544, 15325986176,
34815334374784, 15342763648, 15351151744, 15359540608, 15367929728,
34915376318336, 15384706432, 15393092992, 15401481856, 15409869952,
35015418258816, 15426649984, 15435037568, 15443425664, 15451815296,
35115460203392, 15468589184, 15476979328, 15485369216, 15493755776,
35215502146944, 15510534272, 15518924416, 15527311232, 15535699072,
35315544089472, 15552478336, 15560866688, 15569254528, 15577642624,
35415586031488, 15594419072, 15602809472, 15611199104, 15619586432,
35515627975296, 15636364928, 15644753792, 15653141888, 15661529216,
35615669918848, 15678305152, 15686696576, 15695083136, 15703474048,
35715711861632, 15720251264, 15728636288, 15737027456, 15745417088,
35815753804928, 15762194048, 15770582656, 15778971008, 15787358336,
35915795747712, 15804132224, 15812523392, 15820909696, 15829300096,
36015837691264, 15846071936, 15854466944, 15862855808, 15871244672,
36115879634816, 15888020608, 15896409728, 15904799104, 15913185152,
36215921577088, 15929966464, 15938354816, 15946743424, 15955129472,
36315963519872, 15971907968, 15980296064, 15988684928, 15997073024,
36416005460864, 16013851264, 16022241152, 16030629248, 16039012736,
36516047406976, 16055794816, 16064181376, 16072571264, 16080957824,
36616089346688, 16097737856, 16106125184, 16114514816, 16122904192,
36716131292544, 16139678848, 16148066944, 16156453504, 16164839552,
36816173236096, 16181623424, 16190012032, 16198401152, 16206790528,
36916215177344, 16223567744, 16231956352, 16240344704, 16248731008,
37016257117824, 16265504384, 16273898624, 16282281856, 16290668672,
37116299064192, 16307449216, 16315842176, 16324230016, 16332613504,
37216341006464, 16349394304, 16357783168, 16366172288, 16374561664,
37316382951296, 16391337856, 16399726208, 16408116352, 16416505472,
37416424892032, 16433282176, 16441668224, 16450058624, 16458448768,
37516466836864, 16475224448, 16483613056, 16492001408, 16500391808,
37616508779648, 16517166976, 16525555328, 16533944192, 16542330752,
37716550719616, 16559110528, 16567497088, 16575888512, 16584274816,
37816592665472, 16601051008, 16609442944, 16617832064, 16626218624,
37916634607488, 16642996096, 16651385728, 16659773824, 16668163712,
38016676552576, 16684938112, 16693328768, 16701718144, 16710095488,
38116718492288, 16726883968, 16735272832, 16743661184, 16752049792,
38216760436608, 16768827008, 16777214336, 16785599104, 16793992832,
38316802381696, 16810768768, 16819151744, 16827542656, 16835934848,
38416844323712, 16852711552, 16861101952, 16869489536, 16877876864,
38516886265728, 16894653056, 16903044736, 16911431296, 16919821696,
38616928207488, 16936592768, 16944987776, 16953375616, 16961763968,
38716970152832, 16978540928, 16986929536, 16995319168, 17003704448,
38817012096896, 17020481152, 17028870784, 17037262208, 17045649536,
38917054039936, 17062426496, 17070814336, 17079205504, 17087592064,
39017095978112, 17104369024, 17112759424, 17121147776, 17129536384,
39117137926016, 17146314368, 17154700928, 17163089792, 17171480192,
39217179864192, 17188256896, 17196644992, 17205033856, 17213423488,
39317221811072, 17230198912, 17238588032, 17246976896, 17255360384,
39417263754624, 17272143232, 17280530048, 17288918912, 17297309312,
39517305696384, 17314085504, 17322475136, 17330863744, 17339252096,
39617347640192, 17356026496, 17364413824, 17372796544, 17381190016,
39717389583488, 17397972608, 17406360704, 17414748544, 17423135872,
39817431527296, 17439915904, 17448303232, 17456691584, 17465081728,
39917473468288, 17481857408, 17490247552, 17498635904, 17507022464,
40017515409024, 17523801728, 17532189824, 17540577664, 17548966016,
40117557353344, 17565741184, 17574131584, 17582519168, 17590907008,
40217599296128, 17607687808, 17616076672, 17624455808, 17632852352,
40317641238656, 17649630848, 17658018944, 17666403968, 17674794112,
40417683178368, 17691573376, 17699962496, 17708350592, 17716739968,
40517725126528, 17733517184, 17741898112, 17750293888, 17758673024,
40617767070336, 17775458432, 17783848832, 17792236928, 17800625536,
40717809012352, 17817402752, 17825785984, 17834178944, 17842563968,
40817850955648, 17859344512, 17867732864, 17876119424, 17884511872,
40917892900224, 17901287296, 17909677696, 17918058112, 17926451072,
41017934843776, 17943230848, 17951609216, 17960008576, 17968397696,
41117976784256, 17985175424, 17993564032, 18001952128, 18010339712,
41218018728576, 18027116672, 18035503232, 18043894144, 18052283264,
41318060672128, 18069056384, 18077449856, 18085837184, 18094225792,
41418102613376, 18111004544, 18119388544, 18127781248, 18136170368,
41518144558976, 18152947328, 18161336192, 18169724288, 18178108544,
41618186498944, 18194886784, 18203275648, 18211666048, 18220048768,
41718228444544, 18236833408, 18245220736]
418
419cache_sizes = [
42016776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072,
42117693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088,
42218611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208,
42319529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968,
42420446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216,
42521364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104,
42622281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096,
42723198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112,
42824116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488,
42925034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096,
43025951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472,
43126869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744,
43227786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504,
43328700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752,
43429621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976,
43530538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248,
43631456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392,
43732372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768,
43833289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992,
43934208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984,
44035127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976,
44136044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656,
44236961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904,
44337879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672,
44438795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632,
44539713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032,
44640631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304,
44741547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912,
44842467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696,
44943382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432,
45044302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448,
45145219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208,
45246136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328,
45347053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936,
45447971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312,
45548889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712,
45649807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472,
45750724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848,
45851641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968,
45952557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576,
46053475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744,
46154394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248,
46255312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856,
46356228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488,
46457146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632,
46558064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984,
46658981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512,
46759897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968,
46860817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752,
46961733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512,
47062651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656,
47163569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392,
47264486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792,
47365402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296,
47466321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672,
47567239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304,
47668157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912,
47769074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184,
47869989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816,
47970907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168,
48071826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568,
48172744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944,
48273662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832,
48374579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544,
48475497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072,
48576414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832,
48677331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336,
48778249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664,
48879166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472,
48980084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848,
49081002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304,
49181919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984,
49282835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464,
49383753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608,
49484672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496,
49585589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112,
49686506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632,
49787424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264,
49888341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384,
49989259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376,
50090177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776,
50191093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384,
50292012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912,
50392926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136,
50493845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896,
50594764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016,
50695681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544,
50796599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536,
50897517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168,
50998434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928,
51099352384, 99482816, 99614272, 99745472, 99876416, 100007104,
511100138048, 100267072, 100401088, 100529984, 100662592, 100791872,
512100925248, 101056064, 101187392, 101317952, 101449408, 101580608,
513101711296, 101841728, 101973824, 102104896, 102235712, 102366016,
514102498112, 102628672, 102760384, 102890432, 103021888, 103153472,
515103284032, 103415744, 103545152, 103677248, 103808576, 103939648,
516104070976, 104201792, 104332736, 104462528, 104594752, 104725952,
517104854592, 104988608, 105118912, 105247808, 105381184, 105511232,
518105643072, 105774784, 105903296, 106037056, 106167872, 106298944,
519106429504, 106561472, 106691392, 106822592, 106954304, 107085376,
520107216576, 107346368, 107478464, 107609792, 107739712, 107872192,
521108003136, 108131392, 108265408, 108396224, 108527168, 108657344,
522108789568, 108920384, 109049792, 109182272, 109312576, 109444928,
523109572928, 109706944, 109837888, 109969088, 110099648, 110230976,
524110362432, 110492992, 110624704, 110755264, 110886208, 111017408,
525111148864, 111279296, 111410752, 111541952, 111673024, 111803456,
526111933632, 112066496, 112196416, 112328512, 112457792, 112590784,
527112715968, 112852672, 112983616, 113114944, 113244224, 113376448,
528113505472, 113639104, 113770304, 113901376, 114031552, 114163264,
529114294592, 114425536, 114556864, 114687424, 114818624, 114948544,
530115080512, 115212224, 115343296, 115473472, 115605184, 115736128,
531115867072, 115997248, 116128576, 116260288, 116391488, 116522944,
532116652992, 116784704, 116915648, 117046208, 117178304, 117308608,
533117440192, 117569728, 117701824, 117833024, 117964096, 118094656,
534118225984, 118357312, 118489024, 118617536, 118749632, 118882112,
535119012416, 119144384, 119275328, 119406016, 119537344, 119668672,
536119798464, 119928896, 120061376, 120192832, 120321728, 120454336,
537120584512, 120716608, 120848192, 120979136, 121109056, 121241408,
538121372352, 121502912, 121634752, 121764416, 121895744, 122027072,
539122157632, 122289088, 122421184, 122550592, 122682944, 122813888,
540122945344, 123075776, 123207488, 123338048, 123468736, 123600704,
541123731264, 123861952, 123993664, 124124608, 124256192, 124386368,
542124518208, 124649024, 124778048, 124911296, 125041088, 125173696,
543125303744, 125432896, 125566912, 125696576, 125829056, 125958592,
544126090304, 126221248, 126352832, 126483776, 126615232, 126746432,
545126876608, 127008704, 127139392, 127270336, 127401152, 127532224,
546127663552, 127794752, 127925696, 128055232, 128188096, 128319424,
547128449856, 128581312, 128712256, 128843584, 128973632, 129103808,
548129236288, 129365696, 129498944, 129629888, 129760832, 129892288,
549130023104, 130154048, 130283968, 130416448, 130547008, 130678336,
550130807616, 130939456, 131071552, 131202112, 131331776, 131464384,
551131594048, 131727296, 131858368, 131987392, 132120256, 132250816,
552132382528, 132513728, 132644672, 132774976, 132905792, 133038016,
553133168832, 133299392, 133429312, 133562048, 133692992, 133823296,
554133954624, 134086336, 134217152, 134348608, 134479808, 134607296,
555134741056, 134872384, 135002944, 135134144, 135265472, 135396544,
556135527872, 135659072, 135787712, 135921472, 136052416, 136182848,
557136313792, 136444864, 136576448, 136707904, 136837952, 136970048,
558137099584, 137232064, 137363392, 137494208, 137625536, 137755712,
559137887424, 138018368, 138149824, 138280256, 138411584, 138539584,
560138672832, 138804928, 138936128, 139066688, 139196864, 139328704,
561139460032, 139590208, 139721024, 139852864, 139984576, 140115776,
562140245696, 140376512, 140508352, 140640064, 140769856, 140902336,
563141032768, 141162688, 141294016, 141426496, 141556544, 141687488,
564141819584, 141949888, 142080448, 142212544, 142342336, 142474432,
565142606144, 142736192, 142868288, 142997824, 143129408, 143258944,
566143392448, 143523136, 143653696, 143785024, 143916992, 144045632,
567144177856, 144309184, 144440768, 144570688, 144701888, 144832448,
568144965056, 145096384, 145227584, 145358656, 145489856, 145620928,
569145751488, 145883072, 146011456, 146144704, 146275264, 146407232,
570146538176, 146668736, 146800448, 146931392, 147062336, 147193664,
571147324224, 147455936, 147586624, 147717056, 147848768, 147979456,
572148110784, 148242368, 148373312, 148503232, 148635584, 148766144,
573148897088, 149028416, 149159488, 149290688, 149420224, 149551552,
574149683136, 149814976, 149943616, 150076352, 150208064, 150338624,
575150470464, 150600256, 150732224, 150862784, 150993088, 151125952,
576151254976, 151388096, 151519168, 151649728, 151778752, 151911104,
577152042944, 152174144, 152304704, 152435648, 152567488, 152698816,
578152828992, 152960576, 153091648, 153222976, 153353792, 153484096,
579153616192, 153747008, 153878336, 154008256, 154139968, 154270912,
580154402624, 154533824, 154663616, 154795712, 154926272, 155057984,
581155188928, 155319872, 155450816, 155580608, 155712064, 155843392,
582155971136, 156106688, 156237376, 156367424, 156499264, 156630976,
583156761536, 156892352, 157024064, 157155008, 157284416, 157415872,
584157545536, 157677248, 157810496, 157938112, 158071744, 158203328,
585158334656, 158464832, 158596288, 158727616, 158858048, 158988992,
586159121216, 159252416, 159381568, 159513152, 159645632, 159776192,
587159906496, 160038464, 160169536, 160300352, 160430656, 160563008,
588160693952, 160822208, 160956352, 161086784, 161217344, 161349184,
589161480512, 161611456, 161742272, 161873216, 162002752, 162135872,
590162266432, 162397888, 162529216, 162660032, 162790976, 162922048,
591163052096, 163184576, 163314752, 163446592, 163577408, 163707968,
592163839296, 163969984, 164100928, 164233024, 164364224, 164494912,
593164625856, 164756672, 164887616, 165019072, 165150016, 165280064,
594165412672, 165543104, 165674944, 165805888, 165936832, 166067648,
595166198336, 166330048, 166461248, 166591552, 166722496, 166854208,
596166985408, 167116736, 167246656, 167378368, 167508416, 167641024,
597167771584, 167903168, 168034112, 168164032, 168295744, 168427456,
598168557632, 168688448, 168819136, 168951616, 169082176, 169213504,
599169344832, 169475648, 169605952, 169738048, 169866304, 169999552,
600170131264, 170262464, 170393536, 170524352, 170655424, 170782016,
601170917696, 171048896, 171179072, 171310784, 171439936, 171573184,
602171702976, 171835072, 171966272, 172097216, 172228288, 172359232,
603172489664, 172621376, 172747712, 172883264, 173014208, 173144512,
604173275072, 173407424, 173539136, 173669696, 173800768, 173931712,
605174063424, 174193472, 174325696, 174455744, 174586816, 174718912,
606174849728, 174977728, 175109696, 175242688, 175374272, 175504832,
607175636288, 175765696, 175898432, 176028992, 176159936, 176291264,
608176422592, 176552512, 176684864, 176815424, 176946496, 177076544,
609177209152, 177340096, 177470528, 177600704, 177731648, 177864256,
610177994816, 178126528, 178257472, 178387648, 178518464, 178650176,
611178781888, 178912064, 179044288, 179174848, 179305024, 179436736,
612179568448, 179698496, 179830208, 179960512, 180092608, 180223808,
613180354752, 180485696, 180617152, 180748096, 180877504, 181009984,
614181139264, 181272512, 181402688, 181532608, 181663168, 181795136,
615181926592, 182057536, 182190016, 182320192, 182451904, 182582336,
616182713792, 182843072, 182976064, 183107264, 183237056, 183368384,
617183494848, 183631424, 183762752, 183893824, 184024768, 184154816,
618184286656, 184417984, 184548928, 184680128, 184810816, 184941248,
619185072704, 185203904, 185335616, 185465408, 185596352, 185727296,
620185859904, 185989696, 186121664, 186252992, 186383552, 186514112,
621186645952, 186777152, 186907328, 187037504, 187170112, 187301824,
622187429184, 187562048, 187693504, 187825472, 187957184, 188087104,
623188218304, 188349376, 188481344, 188609728, 188743616, 188874304,
624189005248, 189136448, 189265088, 189396544, 189528128, 189660992,
625189791936, 189923264, 190054208, 190182848, 190315072, 190447424,
626190577984, 190709312, 190840768, 190971328, 191102656, 191233472,
627191364032, 191495872, 191626816, 191758016, 191888192, 192020288,
628192148928, 192282176, 192413504, 192542528, 192674752, 192805952,
629192937792, 193068608, 193198912, 193330496, 193462208, 193592384,
630193723456, 193854272, 193985984, 194116672, 194247232, 194379712,
631194508352, 194641856, 194772544, 194900672, 195035072, 195166016,
632195296704, 195428032, 195558592, 195690304, 195818176, 195952576,
633196083392, 196214336, 196345792, 196476736, 196607552, 196739008,
634196869952, 197000768, 197130688, 197262784, 197394368, 197523904,
635197656384, 197787584, 197916608, 198049472, 198180544, 198310208,
636198442432, 198573632, 198705088, 198834368, 198967232, 199097792,
637199228352, 199360192, 199491392, 199621696, 199751744, 199883968,
638200014016, 200146624, 200276672, 200408128, 200540096, 200671168,
639200801984, 200933312, 201062464, 201194944, 201326144, 201457472,
640201588544, 201719744, 201850816, 201981632, 202111552, 202244032,
641202374464, 202505152, 202636352, 202767808, 202898368, 203030336,
642203159872, 203292608, 203423296, 203553472, 203685824, 203816896,
643203947712, 204078272, 204208192, 204341056, 204472256, 204603328,
644204733888, 204864448, 204996544, 205125568, 205258304, 205388864,
645205517632, 205650112, 205782208, 205913536, 206044736, 206176192,
646206307008, 206434496, 206569024, 206700224, 206831168, 206961856,
647207093056, 207223616, 207355328, 207486784, 207616832, 207749056,
648207879104, 208010048, 208141888, 208273216, 208404032, 208534336,
649208666048, 208796864, 208927424, 209059264, 209189824, 209321792,
650209451584, 209582656, 209715136, 209845568, 209976896, 210106432,
651210239296, 210370112, 210501568, 210630976, 210763712, 210894272,
652211024832, 211156672, 211287616, 211418176, 211549376, 211679296,
653211812032, 211942592, 212074432, 212204864, 212334016, 212467648,
654212597824, 212727616, 212860352, 212991424, 213120832, 213253952,
655213385024, 213515584, 213645632, 213777728, 213909184, 214040128,
656214170688, 214302656, 214433728, 214564544, 214695232, 214826048,
657214956992, 215089088, 215219776, 215350592, 215482304, 215613248,
658215743552, 215874752, 216005312, 216137024, 216267328, 216399296,
659216530752, 216661696, 216790592, 216923968, 217054528, 217183168,
660217316672, 217448128, 217579072, 217709504, 217838912, 217972672,
661218102848, 218233024, 218364736, 218496832, 218627776, 218759104,
662218888896, 219021248, 219151936, 219281728, 219413056, 219545024,
663219675968, 219807296, 219938624, 220069312, 220200128, 220331456,
664220461632, 220592704, 220725184, 220855744, 220987072, 221117888,
665221249216, 221378368, 221510336, 221642048, 221772736, 221904832,
666222031808, 222166976, 222297536, 222428992, 222559936, 222690368,
667222820672, 222953152, 223083968, 223213376, 223345984, 223476928,
668223608512, 223738688, 223869376, 224001472, 224132672, 224262848,
669224394944, 224524864, 224657344, 224788288, 224919488, 225050432,
670225181504, 225312704, 225443776, 225574592, 225704768, 225834176,
671225966784, 226097216, 226229824, 226360384, 226491712, 226623424,
672226754368, 226885312, 227015104, 227147456, 227278528, 227409472,
673227539904, 227669696, 227802944, 227932352, 228065216, 228196288,
674228326464, 228457792, 228588736, 228720064, 228850112, 228981056,
675229113152, 229243328, 229375936, 229505344, 229636928, 229769152,
676229894976, 230030272, 230162368, 230292416, 230424512, 230553152,
677230684864, 230816704, 230948416, 231079616, 231210944, 231342016,
678231472448, 231603776, 231733952, 231866176, 231996736, 232127296,
679232259392, 232388672, 232521664, 232652608, 232782272, 232914496,
680233043904, 233175616, 233306816, 233438528, 233569984, 233699776,
681233830592, 233962688, 234092224, 234221888, 234353984, 234485312,
682234618304, 234749888, 234880832, 235011776, 235142464, 235274048,
683235403456, 235535936, 235667392, 235797568, 235928768, 236057152,
684236190272, 236322752, 236453312, 236583616, 236715712, 236846528,
685236976448, 237108544, 237239104, 237371072, 237501632, 237630784,
686237764416, 237895232, 238026688, 238157632, 238286912, 238419392,
687238548032, 238681024, 238812608, 238941632, 239075008, 239206336,
688239335232, 239466944, 239599168, 239730496, 239861312, 239992384,
689240122816, 240254656, 240385856, 240516928, 240647872, 240779072,
690240909632, 241040704, 241171904, 241302848, 241433408, 241565248,
691241696192, 241825984, 241958848, 242088256, 242220224, 242352064,
692242481856, 242611648, 242744896, 242876224, 243005632, 243138496,
693243268672, 243400384, 243531712, 243662656, 243793856, 243924544,
694244054592, 244187072, 244316608, 244448704, 244580032, 244710976,
695244841536, 244972864, 245104448, 245233984, 245365312, 245497792,
696245628736, 245759936, 245889856, 246021056, 246152512, 246284224,
697246415168, 246545344, 246675904, 246808384, 246939584, 247070144,
698247199552, 247331648, 247463872, 247593536, 247726016, 247857088,
699247987648, 248116928, 248249536, 248380736, 248512064, 248643008,
700248773312, 248901056, 249036608, 249167552, 249298624, 249429184,
701249560512, 249692096, 249822784, 249954112, 250085312, 250215488,
702250345792, 250478528, 250608704, 250739264, 250870976, 251002816,
703251133632, 251263552, 251395136, 251523904, 251657792, 251789248,
704251919424, 252051392, 252182464, 252313408, 252444224, 252575552,
705252706624, 252836032, 252968512, 253099712, 253227584, 253361728,
706253493056, 253623488, 253754432, 253885504, 254017216, 254148032,
707254279488, 254410432, 254541376, 254672576, 254803264, 254933824,
708255065792, 255196736, 255326528, 255458752, 255589952, 255721408,
709255851072, 255983296, 256114624, 256244416, 256374208, 256507712,
710256636096, 256768832, 256900544, 257031616, 257162176, 257294272,
711257424448, 257555776, 257686976, 257818432, 257949632, 258079552,
712258211136, 258342464, 258473408, 258603712, 258734656, 258867008,
713258996544, 259127744, 259260224, 259391296, 259522112, 259651904,
714259784384, 259915328, 260045888, 260175424, 260308544, 260438336,
715260570944, 260700992, 260832448, 260963776, 261092672, 261226304,
716261356864, 261487936, 261619648, 261750592, 261879872, 262011968,
717262143424, 262274752, 262404416, 262537024, 262667968, 262799296,
718262928704, 263061184, 263191744, 263322944, 263454656, 263585216,
719263716672, 263847872, 263978944, 264108608, 264241088, 264371648,
720264501184, 264632768, 264764096, 264895936, 265024576, 265158464,
721265287488, 265418432, 265550528, 265681216, 265813312, 265943488,
722266075968, 266206144, 266337728, 266468032, 266600384, 266731072,
723266862272, 266993344, 267124288, 267255616, 267386432, 267516992,
724267648704, 267777728, 267910592, 268040512, 268172096, 268302784,
725268435264, 268566208, 268696256, 268828096, 268959296, 269090368,
726269221312, 269352256, 269482688, 269614784, 269745856, 269876416,
727270007616, 270139328, 270270272, 270401216, 270531904, 270663616,
728270791744, 270924736, 271056832, 271186112, 271317184, 271449536,
729271580992, 271711936, 271843136, 271973056, 272105408, 272236352,
730272367296, 272498368, 272629568, 272759488, 272891456, 273022784,
731273153856, 273284672, 273415616, 273547072, 273677632, 273808448,
732273937088, 274071488, 274200896, 274332992, 274463296, 274595392,
733274726208, 274857536, 274988992, 275118656, 275250496, 275382208,
734275513024, 275643968, 275775296, 275906368, 276037184, 276167872,
735276297664, 276429376, 276560576, 276692672, 276822976, 276955072,
736277085632, 277216832, 277347008, 277478848, 277609664, 277740992,
737277868608, 278002624, 278134336, 278265536, 278395328, 278526784,
738278657728, 278789824, 278921152, 279052096, 279182912, 279313088,
739279443776, 279576256, 279706048, 279838528, 279969728, 280099648,
740280230976, 280361408, 280493632, 280622528, 280755392, 280887104,
741281018176, 281147968, 281278912, 281411392, 281542592, 281673152,
742281803712, 281935552, 282066496, 282197312, 282329024, 282458816,
743282590272, 282720832, 282853184, 282983744, 283115072, 283246144,
744283377344, 283508416, 283639744, 283770304,