原文🔗：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 ]
