Ethash
原文🔗:Ethash REVISION 23
Ethash是Ethereum 1.0使用的PoW算法。尽管它不能再适当地被称为Dagger-Hashimoto的最新版本,因为这两种算法的许多原始特征发生了巨大的变化。查看https://github.com/ethereum/wiki/blob/master/Dagger-Hashimoto.md的原始版本。
算法所采用的一般路线如下:
- 存在一个种子,可以通过扫描区块头直到该点来计算每个块。
- 从种子中,可以计算一个16 MB的伪随机缓存。Light客户端存储缓存。
- 从缓存中,我们可以生成一个1 GB的数据集,其属性为数据集中每个仅依赖于缓存中的少量项目。完整的客户和矿工存储数据集。数据集随时间线性增长。
- 挖掘包括抓取数据集的随机切片并将它们散列在一起。通过使用缓存重新生成所需数据集的特定片段,可以使用低内存完成验证,因此您只需存储缓存。
大型数据集每30000块更新一次,因此绝大多数矿工的努力将会读取数据集,而不是对其进行更改。
有关此算法的设计原理考虑,请参阅https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale。
定义
我们采用以下定义:
WORD_BYTES = 4 # bytes in word
DATASET_BYTES_INIT = 2**30 # bytes in dataset at genesis
DATASET_BYTES_GROWTH = 2**23 # dataset growth per epoch
CACHE_BYTES_INIT = 2**24 # bytes in cache at genesis
CACHE_BYTES_GROWTH = 2**17 # cache growth per epoch
CACHE_MULTIPLIER=1024 # Size of the DAG relative to the cache
EPOCH_LENGTH = 30000 # blocks per epoch
MIX_BYTES = 128 # width of mix
HASH_BYTES = 64 # hash length in bytes
DATASET_PARENTS = 256 # number of parents of each dataset element
CACHE_ROUNDS = 3 # number of rounds in cache production
ACCESSES = 64 # number of accesses in hashimoto loop
关于本规范中描述的“SHA3”散列的注释
以太坊的发展与SHA3标准的发展一致,并且标准过程对最终散列算法的填充做了一个最新变更,因此以太坊的“sha3_256”和“sha3_512”散列不是标准sha3散列,而是一个经常提到的变体在其他情况下为“Keccak-256”和“Keccak-512”。参见讨论,例如在Rename/alias sha3 to minimize confusion with SHA-3 standard #59,在Which cryptographic hash function does Ethereum use?或What is the approach to calculate an Ethereum address from a 256 bit private key?。
请记住这一点,因为在下面的算法描述中提到了“sha3”散列。
参数
Ethash的缓存和数据集的参数取决于区块号。缓存大小和数据集大小都线性增长; 然而,我们总是采用低于线性增长阈值的最高素数,以降低意外规律性导致循环行为的风险。
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
# Sequentially produce the initial dataset
o = [sha3_512(seed)]
for i in range(1, n):
o.append(sha3_512(o[-1]))
# Use a low-round version of 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内存,然后从严格内存硬散列函数(2014)中执行两次Sergio Demian Lerner的RandMemoHash
算法。输出是一组524288个64字节值。
数据聚合功能
在某些情况下,我们使用受FNV hash启发的算法作为XOR
的非关联替代。请注意,我们将素数与完整的32位输入相乘,与将素数依次乘以一个字节(八位字节)的FNV-1规格相反。
FNV_PRIME = 0x01000193
def fnv(v1, v2):
return ((v1 * FNV_PRIME) ^ v2) % 2**32
请注意,由于黄皮书上指定fnv为v1 *(FNV_PRIME ^ v2)
,所有当前实现一致地使用上述定义。
完整的数据集计算
整个1 GB数据集中的每个64字节的item计算如下:
def calc_dataset_item(cache, i):
n = len(cache)
r = HASH_BYTES // WORD_BYTES
# initialize the mix
mix = copy.copy(cache[i % n])
mix[0] ^= i
mix = sha3_512(mix)
# fnv it with a lot of random cache nodes based on i
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)]
Main Loop
现在,我们指定主要的“hashimoto”式循环,在这里我们汇总来自整个数据集的数据,以便为特定的区块头和随机数生成我们的最终值。在下面的代码,header
表示基于SHA3-256散列以RLP编码的一个截断区块头,即不包括mixHash
和nonce
字段的区块头。nonce
是大端序列的64位无符号整数的八个字节。所以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
# combine header+nonce into a 64 byte seed
s = sha3_512(header + nonce[::-1])
# start the mix with replicated s
mix = []
for _ in range(MIX_BYTES / HASH_BYTES):
mix.extend(s)
# mix in random dataset nodes
for i in range(ACCESSES):
p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
newdata = []
for j in range(MIX_BYTES / HASH_BYTES):
newdata.extend(dataset_lookup(p + j))
mix = map(fnv, mix, newdata)
# compress mix
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字节的"mix",并从整个数据集中重复顺序获取128个字节,并使用该fnv函数将其与"mix"进行组合。使用128字节的顺序访问,以便算法的每一轮总是从RAM中提取整个页面,从而最大限度地减少ASIC在理论上能够避免的数据翻译遗漏。
如果此算法的输出低于所需目标,则该随机数是有效的。请注意,最后的额外应用程序sha3_256
确保存在可以提供的中间随机数,以证明至少进行了少量工作; 这个快速外部PoW验证可以用于反DDoS的目的。它还可以提供统计保证,结果是一个256位数字。
挖矿
挖矿算法定义如下:
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
# Assumes little endian bit ordering (same as Intel architectures)
def decode_int(s):
return int(s[::-1].encode('hex'), 16) if s else 0
def encode_int(s):
a = "%x" % s
return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]
def zpad(s, length):
return s + '\x00' * max(0, length - len(s))
def serialize_hash(h):
return ''.join([zpad(encode_int(x), 4) for x in h])
def deserialize_hash(h):
return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
def hash_words(h, sz, x):
if isinstance(x, list):
x = serialize_hash(x)
y = h(x)
return deserialize_hash(y)
def serialize_cache(ds):
return ''.join([serialize_hash(h) for h in ds])
serialize_dataset = serialize_cache
# sha3 hash function, outputs 64 bytes
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个数据大小和缓存大小的制表。它们是用这里提供的Mathematica函数生成的:
def get_datasize(block_number):
返回 data_sizes [block_number // EPOCH_LENGTH ]
def get_cachesize(block_number):
返回 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 ]