ایتھ ہیش
ایتھ ہیش ایتھیریم کا ثبوتِ کار (PoW) کان کنی کا الگورتھم تھا۔ ثبوتِ کار (PoW) کو اب مکمل طور پر بند کر دیا گیا ہے اور ایتھیریم اب اس کے بجائے حصہ داری کا ثبوت (PoS) کا استعمال کرتے ہوئے محفوظ ہے۔ دی مرج، حصہ داری کا ثبوت (PoS) اور اسٹیکنگ کے بارے میں مزید پڑھیں۔ یہ صفحہ تاریخی دلچسپی کے لیے ہے!
ایتھ ہیش Dagger-Hashimoto الگورتھم کا ایک ترمیم شدہ ورژن ہے۔ ایتھ ہیش ثبوتِ کار (PoW) میموری ہارڈ (opens in a new tab) ہے، جس کے بارے میں خیال کیا جاتا تھا کہ یہ الگورتھم کو ASIC کے خلاف مزاحم بناتا ہے۔ بالآخر ایتھ ہیش ASIC تیار کر لیے گئے لیکن ثبوتِ کار (PoW) کے بند ہونے تک GPU کان کنی اب بھی ایک قابل عمل آپشن تھا۔ ایتھ ہیش اب بھی دیگر غیر ایتھیریم ثبوتِ کار (PoW) نیٹ ورکس پر دیگر کوائنز کی کان کنی کے لیے استعمال ہوتا ہے۔
ایتھ ہیش کیسے کام کرتا ہے؟
میموری ہارڈنیس ایک ثبوتِ کار (PoW) الگورتھم کے ساتھ حاصل کی جاتی ہے جس کے لیے نانس اور بلاک ہیڈر پر منحصر ایک مقررہ وسیلے کے ذیلی سیٹس (subsets) کا انتخاب درکار ہوتا ہے۔ اس وسیلے (جس کا سائز چند گیگا بائٹس ہوتا ہے) کو DAG کہا جاتا ہے۔ DAG کو ہر 30,000 بلاکس کے بعد تبدیل کیا جاتا ہے، جو کہ تقریباً 125 گھنٹے کا دورانیہ ہے جسے ایک دور (epoch) کہا جاتا ہے (تقریباً 5.2 دن) اور اسے بننے میں کچھ وقت لگتا ہے۔ چونکہ DAG کا انحصار صرف بلاک کی اونچائی پر ہوتا ہے، اس لیے اسے پہلے سے تیار کیا جا سکتا ہے، لیکن اگر ایسا نہیں ہے تو کلائنٹ کو بلاک تیار کرنے کے لیے اس عمل کے اختتام تک انتظار کرنا پڑتا ہے۔ اگر کلائنٹس وقت سے پہلے DAGs کو تیار اور کیش (cache) نہیں کرتے ہیں تو نیٹ ورک کو ہر دور کی منتقلی پر بلاک میں بڑے پیمانے پر تاخیر کا سامنا کرنا پڑ سکتا ہے۔ نوٹ کریں کہ ثبوتِ کار (PoW) کی تصدیق کے لیے DAG تیار کرنے کی ضرورت نہیں ہے، جو بنیادی طور پر کم CPU اور چھوٹی میموری دونوں کے ساتھ تصدیق کی اجازت دیتا ہے۔
الگورتھم کا عمومی طریقہ کار درج ذیل ہے:
- ایک سیڈ (seed) موجود ہوتا ہے جس کا حساب ہر بلاک کے لیے اس مقام تک بلاک ہیڈرز کو اسکین کر کے لگایا جا سکتا ہے۔
- سیڈ سے، کوئی بھی 16 MB کا سیڈورینڈم کیش (pseudorandom cache) شمار کر سکتا ہے۔ لائٹ کلائنٹس کیش کو اسٹور کرتے ہیں۔
- کیش سے، ہم ایک 1 GB کا ڈیٹاسیٹ تیار کر سکتے ہیں، اس خصوصیت کے ساتھ کہ ڈیٹاسیٹ میں موجود ہر آئٹم کا انحصار کیش کے صرف چند آئٹمز پر ہوتا ہے۔ فل کلائنٹس اور کان کن ڈیٹاسیٹ کو اسٹور کرتے ہیں۔ ڈیٹاسیٹ وقت کے ساتھ لکیری (linearly) طور پر بڑھتا ہے۔
- کان کنی میں ڈیٹاسیٹ کے بے ترتیب حصوں کو پکڑنا اور انہیں ایک ساتھ ہیشنگ کرنا شامل ہے۔ تصدیق کم میموری کے ساتھ کیش کا استعمال کرتے ہوئے ڈیٹاسیٹ کے ان مخصوص حصوں کو دوبارہ تیار کر کے کی جا سکتی ہے جن کی آپ کو ضرورت ہے، لہذا آپ کو صرف کیش کو اسٹور کرنے کی ضرورت ہے۔
بڑے ڈیٹاسیٹ کو ہر 30,000 بلاکس میں ایک بار اپ ڈیٹ کیا جاتا ہے، لہذا کان کن کی زیادہ تر کوشش ڈیٹاسیٹ کو پڑھنے میں صرف ہوگی، نہ کہ اس میں تبدیلیاں کرنے میں۔
تعریفیں
ہم درج ذیل تعریفیں استعمال کرتے ہیں:
WORD_BYTES = 4 # لفظ میں بائٹس
DATASET_BYTES_INIT = 2**30 # جینیسس پر ڈیٹاسیٹ میں بائٹس
DATASET_BYTES_GROWTH = 2**23 # فی دور ڈیٹاسیٹ کی نمو
CACHE_BYTES_INIT = 2**24 # جینیسس پر کیش میں بائٹس
CACHE_BYTES_GROWTH = 2**17 # فی دور کیش کی نمو
CACHE_MULTIPLIER=1024 # کیش کے مقابلے میں DAG کا سائز
EPOCH_LENGTH = 30000 # فی دور بلاکس
MIX_BYTES = 128 # مکس کی چوڑائی
HASH_BYTES = 64 # بائٹس میں ہیش کی لمبائی
DATASET_PARENTS = 256 # ہر ڈیٹاسیٹ عنصر کے پیرنٹس کی تعداد
CACHE_ROUNDS = 3 # کیش کی تیاری میں راؤنڈز کی تعداد
ACCESSES = 64 # ہاشیموٹو لوپ میں رسائی کی تعداد
'SHA3' کا استعمال
ایتھیریم کی ترقی SHA3 معیار کی ترقی کے ساتھ ہی ہوئی، اور معیارات کے عمل نے حتمی ہیش الگورتھم کی پیڈنگ میں تاخیر سے تبدیلی کی، تاکہ ایتھیریم کے "sha3_256" اور "sha3_512" ہیشز معیاری sha3 ہیشز نہیں ہیں، بلکہ ایک قسم ہے جسے اکثر دیگر سیاق و سباق میں "کیچاک-۲۵۶" اور "Keccak-512" کہا جاتا ہے۔ بحث دیکھیں، مثال کے طور پر، یہاں (opens in a new tab)، یہاں (opens in a new tab)، یا یہاں (opens in a new tab)۔
براہ کرم اسے ذہن میں رکھیں کیونکہ ذیل میں الگورتھم کی تفصیل میں "sha3" ہیشز کا حوالہ دیا گیا ہے۔
پیرامیٹرز
ایتھ ہیش کے کیش اور ڈیٹاسیٹ کے پیرامیٹرز بلاک نمبر پر منحصر ہیں۔ کیش کا سائز اور ڈیٹاسیٹ کا سائز دونوں لکیری طور پر بڑھتے ہیں؛ تاہم، ہم ہمیشہ لکیری طور پر بڑھنے والی حد سے نیچے سب سے زیادہ پرائم (prime) لیتے ہیں تاکہ حادثاتی باقاعدگیوں کے خطرے کو کم کیا جا سکے جو سائیکلک رویے کا باعث بنتے ہیں۔
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
ڈیٹاسیٹ اور کیش سائز کی اقدار کے جدول ضمیمہ میں فراہم کیے گئے ہیں۔
کیش کی تیاری
اب، ہم کیش تیار کرنے کے لیے فنکشن کی وضاحت کرتے ہیں:
def mkcache(cache_size, seed):
n = cache_size // HASH_BYTES
# ابتدائی ڈیٹاسیٹ بالترتیب تیار کریں
o = [sha3_512(seed)]
for i in range(1, n):
o.append(sha3_512(o[-1]))
# randmemohash کا کم راؤنڈ والا ورژن استعمال کریں
for _ in range(CACHE_ROUNDS):
for i in range(n):
v = o[i][0] % n
o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))
return o
کیش کی تیاری کے عمل میں پہلے ترتیب وار 32 MB میموری کو بھرنا شامل ہے، پھر Strict Memory Hard Hashing Functions (2014) (opens in a new tab) سے Sergio Demian Lerner کے RandMemoHash الگورتھم کے دو پاسز انجام دینا شامل ہے۔ آؤٹ پٹ 524288 64-byte اقدار کا ایک سیٹ ہے۔
ڈیٹا ایگریگیشن فنکشن
ہم کچھ معاملات میں XOR کے غیر متعلقہ متبادل کے طور پر FNV ہیش (opens in a new tab) سے متاثر ایک الگورتھم استعمال کرتے ہیں۔ نوٹ کریں کہ ہم پرائم کو مکمل 32-bit ان پٹ کے ساتھ ضرب دیتے ہیں، اس کے برعکس FNV-1 اسپیک جو پرائم کو باری باری ایک بائٹ (octet) کے ساتھ ضرب دیتا ہے۔
FNV_PRIME = 0x01000193
def fnv(v1, v2):
return ((v1 * FNV_PRIME) ^ v2) % 2**32
براہ کرم نوٹ کریں، یہاں تک کہ یلو پیپر fnv کو v1*(FNV_PRIME ^ v2) کے طور پر متعین کرتا ہے، تمام موجودہ نفاذات مستقل طور پر مندرجہ بالا تعریف کا استعمال کرتے ہیں۔
مکمل ڈیٹاسیٹ کا حساب
مکمل 1 GB ڈیٹاسیٹ میں ہر 64-byte آئٹم کا حساب اس طرح لگایا جاتا ہے:
def calc_dataset_item(cache, i):
n = len(cache)
r = HASH_BYTES // WORD_BYTES
# مکس کی ابتدا کریں
mix = copy.copy(cache[i % n])
mix[0] ^= i
mix = sha3_512(mix)
# i کی بنیاد پر اسے بہت سے رینڈم کیشے نوڈز کے ساتھ fnv کریں
for j in range(DATASET_PARENTS):
cache_index = fnv(i ^ j, mix[j % r])
mix = map(fnv, mix, cache[cache_index % n])
return sha3_512(mix)
بنیادی طور پر، ہم 256 سیڈورینڈم طور پر منتخب کردہ کیش نوڈز سے ڈیٹا کو یکجا کرتے ہیں، اور ڈیٹاسیٹ نوڈ کا حساب لگانے کے لیے اسے ہیش کرتے ہیں۔ پھر پورا ڈیٹاسیٹ اس کے ذریعے تیار کیا جاتا ہے:
def calc_dataset(full_size, cache):
return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]
مین لوپ
اب، ہم مرکزی "hashimoto" جیسے لوپ کی وضاحت کرتے ہیں، جہاں ہم ایک مخصوص ہیڈر اور نانس کے لیے اپنی حتمی قدر تیار کرنے کے لیے مکمل ڈیٹاسیٹ سے ڈیٹا اکٹھا کرتے ہیں۔ ذیل کے کوڈ میں، header ایک مختصر بلاک ہیڈر کی RLP نمائندگی کے SHA3-256 ہیش کی نمائندگی کرتا ہے، یعنی ایک ہیڈر جس میں mixHash اور nonce فیلڈز شامل نہیں ہیں۔ nonce بگ اینڈِین ترتیب میں 64 bit غیر دستخط شدہ انٹیجر کے آٹھ بائٹس ہیں۔ لہذا nonce[::-1] اس قدر کی آٹھ بائٹ لٹل اینڈِین نمائندگی ہے:
def hashimoto(header, nonce, full_size, dataset_lookup):
n = full_size / HASH_BYTES
w = MIX_BYTES // WORD_BYTES
mixhashes = MIX_BYTES / HASH_BYTES
# ہیڈر+نانس کو ملا کر 64 بائٹ سیڈ بنائیں
s = sha3_512(header + nonce[::-1])
# نقل شدہ s کے ساتھ مکس شروع کریں
mix = []
for _ in range(MIX_BYTES / HASH_BYTES):
mix.extend(s)
# رینڈم ڈیٹاسیٹ نوڈز شامل کریں
for i in range(ACCESSES):
p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
newdata = []
for j in range(MIX_BYTES / HASH_BYTES):
newdata.extend(dataset_lookup(p + j))
mix = map(fnv, mix, newdata)
# مکس کو کمپریس کریں
cmix = []
for i in range(0, len(mix), 4):
cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))
return {
"mix digest": serialize_hash(cmix),
"result": serialize_hash(sha3_256(s+cmix))
}
def hashimoto_light(full_size, cache, header, nonce):
return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))
def hashimoto_full(full_size, dataset, header, nonce):
return hashimoto(header, nonce, full_size, lambda x: dataset[x])
بنیادی طور پر، ہم 128 bytes چوڑا ایک "مکس" برقرار رکھتے ہیں، اور بار بار ترتیب وار مکمل ڈیٹاسیٹ سے 128 bytes حاصل کرتے ہیں اور اسے مکس کے ساتھ جوڑنے کے لیے fnv فنکشن کا استعمال کرتے ہیں۔ ترتیب وار رسائی کے 128 bytes استعمال کیے جاتے ہیں تاکہ الگورتھم کا ہر راؤنڈ ہمیشہ RAM سے ایک مکمل صفحہ حاصل کرے، جس سے ٹرانسلیشن لک اسائیڈ بفر (translation lookaside buffer) کی کمی کو کم کیا جا سکے جس سے نظریاتی طور پر ASIC بچنے کے قابل ہوں گے۔
اگر اس الگورتھم کا آؤٹ پٹ مطلوبہ ہدف سے کم ہے، تو نانس درست ہے۔ نوٹ کریں کہ آخر میں sha3_256 کا اضافی اطلاق اس بات کو یقینی بناتا ہے کہ ایک درمیانی نانس موجود ہے جو یہ ثابت کرنے کے لیے فراہم کیا جا سکتا ہے کہ کم از کم تھوڑا سا کام کیا گیا تھا؛ یہ فوری بیرونی ثبوتِ کار (PoW) کی تصدیق اینٹی-DDoS مقاصد کے لیے استعمال کی جا سکتی ہے۔ یہ شماریاتی یقین دہانی فراہم کرنے کا بھی کام کرتا ہے کہ نتیجہ ایک غیر جانبدار، 256-bit نمبر ہے۔
کان کنی
کان کنی کے الگورتھم کی تعریف اس طرح کی گئی ہے:
def mine(full_size, dataset, header, difficulty):
# ایک ہی ہندسے پر ہیش کے ساتھ موازنہ کرنے کے لیے ٹارگٹ کو زیرو پیڈ کریں
target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
from random import randint
nonce = randint(0, 2**64)
while hashimoto_full(full_size, dataset, header, nonce) > target:
nonce = (nonce + 1) % 2**64
return nonce
سیڈ ہیش کی تعریف
سیڈ ہیش کا حساب لگانے کے لیے جو کسی دیے گئے بلاک کے اوپر کان کنی کے لیے استعمال کیا جائے گا، ہم درج ذیل الگورتھم استعمال کرتے ہیں:
def get_seedhash(block):
s = '\x00' * 32
for i in range(block.number // EPOCH_LENGTH):
s = serialize_hash(sha3_256(s))
return s
نوٹ کریں کہ ہموار کان کنی اور تصدیق کے لیے، ہم تجویز کرتے ہیں کہ مستقبل کے سیڈ ہیشز اور ڈیٹاسیٹس کو ایک الگ تھریڈ میں پہلے سے شمار کیا جائے۔
مزید مطالعہ
کسی ایسے کمیونٹی وسیلے کے بارے میں جانتے ہیں جس نے آپ کی مدد کی ہو؟ اس صفحے میں ترمیم کریں اور اسے شامل کریں!
ضمیمہ
اگر آپ مندرجہ بالا Python اسپیک کو کوڈ کے طور پر چلانے میں دلچسپی رکھتے ہیں تو درج ذیل کوڈ کو پہلے شامل کیا جانا چاہیے۔
import sha3, copy
# لٹل اینڈِین بٹ کی ترتیب فرض کرتا ہے (انٹیل آرکیٹیکچرز کی طرح)
def decode_int(s):
return int(s[::-1].encode('hex'), 16) if s else 0
def encode_int(s):
a = "%x" % s
return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]
def zpad(s, length):
return s + '\x00' * max(0, length - len(s))
def serialize_hash(h):
return ''.join([zpad(encode_int(x), 4) for x in h])
def deserialize_hash(h):
return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
def hash_words(h, sz, x):
if isinstance(x, list):
x = serialize_hash(x)
y = h(x)
return deserialize_hash(y)
def serialize_cache(ds):
return ''.join([serialize_hash(h) for h in ds])
serialize_dataset = serialize_cache
# sha3 ہیش فنکشن، 64 بائٹس آؤٹ پٹ دیتا ہے
def sha3_512(x):
return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)
def sha3_256(x):
return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)
def xor(a, b):
return a ^ b
def isprime(x):
for i in range(2, int(x**0.5)):
if x % i == 0:
return False
return True
ڈیٹا کے سائز
درج ذیل لک اپ ٹیبلز ڈیٹا سائز اور کیش سائز کے تقریباً 2048 ٹیبولیٹڈ ادوار (epochs) فراہم کرتے ہیں۔
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]