Skip to content

Latest commit

 

History

History
1308 lines (1196 loc) · 70.7 KB

ProgPoW.md

File metadata and controls

1308 lines (1196 loc) · 70.7 KB
Raw

Contents

This spec is REVISION 0.9.1. Whenever you substantively (ie. not clarifications) update the algorithm, please update the revision number in this sentence. Also, in all implementations please include a spec revision number

ProgPoW is the new PoW algorithm for Ethereum. It is based on Ethash the current PoW algorithm for Ethereum see https://github.com/ethereum/wiki/wiki/Ethash. It improves the ASIC resistance of Ethash. However full ASIC resistance is a myth since chip manufacturers can always tune their chips to exceed the hashing capabilities of commodity GPU's. This algorithm should resolve some of the issues of Ethash and lessen the headroom for a speedup that ASIC's can achieve.

The general route that the algorithm takes is as follows:

  1. There exists a seed which can be computed for each block by scanning through the block headers up until that point.
  2. From the seed, one can compute a 16 MB pseudorandom cache. Light clients store the cache.
  3. From the cache, we can generate a 2 GB dataset, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time.
  4. The first bytes of the dag also act as a 16 KB cache set. Full clients and miners store this dataset. This dataset does not grow with time.
  5. Mining involves grabbing random slices of the dataset and the cache set and hashing them together. The main loop also contains random math that helps with ASIC resistance. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache.

The large dataset is updated once every 30000 blocks, so the vast majority of a miner's effort will be reading the dataset, not making changes to it. The random math inside the loop changes every 50 blocks.

See https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale for design rationale considerations for this algorithm.

Definitions

We employ the following definitions:

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
PROGPOW_LANES = 16                # number of parallel lanes used to produce one hash
PROGPOW_REGS = 32                 # size of the mix state 
PROGPOW_PERIOD = 50               # number of blocks after which 
PROGPOW_CACHE_BYTES = 16*1024     # bytes in the cache set
PROGPOW_CNT_DAG = 64              # number of dag accesses in the outer loop
PROGPOW_CNT_CACHE = 12            # number of cache set accesses per loop
PROGPOW_CNT_MATH = 20             # number of math operations per loop
A note regarding "SHA3" hashes described in this specification

Ethereum's development coincided with the development of the SHA3 standard, and the standards process made a late change in the padding of the finalized hash algorithm, so that Ethereum's "sha3_256" and "sha3_512" hashes are not standard sha3 hashes, but a variant often referred to as "Keccak-256" and "Keccak-512" in other contexts. See discussion, e.g. here, here, or here. In order to improve the overhead of keccak we use keccak-f[800] with 800 bits of security. As of now, there are no known attacks to decrease the security of keccak in a way that threatens the security of keccak-f[800]. We use a variant of SHAKE with width=800, bitrate=576, capacity=224, output=256, and without padding. The result of keccak is treated as a 256-bit big-endian number. The MSB of the result is result byte 0.

Please keep that in mind as "sha3" hashes are referred to in the description of the algorithm below.

Parameters

The parameters for ProgPoW's cache and dataset depend on the block number. The cache size and dataset size both grow linearly; however, we always take the highest prime below the linearly growing threshold in order to reduce the risk of accidental regularities leading to cyclic behavior. The cache set does not grow, it is fixed to PROGPOW_CACHE_BYTES bytes.

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 get_cache_set_size():
    return PROGPOW_CACHE_BYTES

Tables of dataset and cache size values are provided in the appendix.

Cache Generation

Now, we specify the function for producing a cache:

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

The cache production process involves first sequentially filling up 32 MB of memory, then performing two passes of Sergio Demian Lerner's RandMemoHash algorithm from Strict Memory Hard Hashing Functions (2014). The output is a set of 524288 64-byte values.

Data aggregation functions

We use an algorithm inspired by the FNV hash in some cases as a non-associative substitute for XOR for the generation of the DAG. Note that we multiply the prime with the full 32-bit input, in contrast with the FNV-1 spec which multiplies the prime with one byte (octet) in turn.

FNV_PRIME = 0x01000193

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

The FNV-1 spec however has some flaws that can be exploited by ASIC's and FPGA's. This flaw can be used to decrease the amount of computation needed in the main loop. We will continue to use FNV-1 for the DAG generation but use FNV-1a in the main loop since it has better distribution properties.

FNV_PRIME = 0x01000193;

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

Please note, even the yellow paper specifies fnv as v1*(FNV_PRIME ^ v2), all current implementations consistently use the above definition.

Full dataset calculation

Each 64-byte item in the full 1 GB dataset is computed as follows:

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)

Essentially, we combine data from 256 pseudorandomly selected cache nodes, and hash that to compute the dataset node. The entire dataset is then generated by:

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

The cache_set is generated as the following:

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

Pseudorandom Number Generator

We use the PRNG KISS99 to generate pseudorandom numbers in our main loop. KISS99 is currently the random number generator that passes the TestU01 testsuite with the fewest instructions. More complex PRNG's can be efficiently implemented in ASIC'S. KISS99 has a period of around 10^37 which is plenty enough for our use-case. KISS99 is not a cryptographicly secure pseudorandom number generator since it is possible to recalculate the seed after observing several outputs of the function. However this is no problem for us, since the seed is public. We only use KISS99 for its good distribution properties.

def kiss99(z , w, jsr, jcong): 
    z = 36969 * (z & 0xffff) + (z >> 16);
    w = 18000 *  (w & 0xffff) + (w >> 16) ;
    jcong = 69069 * jcong + 1234567;
    jsr ^= (jsr << 17);
    jsr ^= (jsr >> 13);
    jsr ^= (jsr << 5);
    return [z,w,jsr,jcong, ((((z << 16) + w) ^ jcong) + jsr) & 0xffffffff];

Random math

ProgPoW includes PROGPOW_CNT_MATH rounds of random math to the main loop. This random math changes every PROGPOW_PERIOD blocks. The following function is used to switch between the math functions. All math functions can be found in the Appendix

def random_math(a, b, r):
    result = {
        0: lambda a, b : a + b,
        1: lambda a, b : a * b,
        2: lambda a, b : (bit64(a * b) >> 32), #mul_hi
        3: lambda a, b : a if a < b else b,    #min(a,b)
        4: lambda a, b : rotl(a, b),
        5: lambda a, b : rotr(a, b),
        6: lambda a, b : a & b,
        7: lambda a, b : a | b,
        8: lambda a, b : a ^ b,
        9: lambda a, b : clz(a) + clz(b),
        10: lambda a, b : popcount(a) + popcount(b)
    }[r](a,b)
    return result & 0xffffffff;

Merge Operation

The merge operation is also chosen uniformely at random to increase the chip size ASIC manifacturers have to spend in order to create a custom ASIC for ProgPoW. The math functions are chosen such that the output remains high entropy even if the second input is of low entropy. We assume that the first input has high entropy.

def merge(a, b, r):
    result = {
        0: lambda a, b : (a * 33) + b,
        1: lambda a, b : (a ^ b) * 33,
        2: lambda a, b : rotl(a, ((r >> 16) % 32)),
        3: lambda a, b : rotr(a, ((r >> 16) % 32)),
    }[r](a,b)
    return result & 0xffffffff;

Fill Mix

ProgPoW maintains a mix state that is initialized through the hash of the random seed.

def fill_mix(seed):
    mix = [] # [PROGPOW_LANES][PROGPOW_REGS];
    fnv_hash = 0x811c9dc5;
    lower = seed & 0xffffffff;
    upper = bit64(seed) >> 32;
    z = fnv1a(fnv_hash, lower);
    w = fnv1a(fnv_hash, upper);
    for l in range(PROGPOW_LANES):
        jsr = fnv1a(fnv_hash, l);
        jcong = fnv1a(fnv_hash, l);
        for r in range(PROGPOW_REGS):
            tmp = kiss99(z, w, jsr, jcong);
            z = tmp[0];
            w = tmp[1];
            jsr = tmp[2];
            jcong = tmp[3];
            mix.append(tmp[4]);
    return mix;

Init

The following function initializes two arrays, the sequence destination and the sequence cache

def progPowInit(seed): #seed is a 64 bit 
    PROGPOW_REGS = 16;
    mix_seq_dst = [];
    mix_seq_cache = [];
    fnv_hash = 0x811c9dc5;
    lower = seed & 0xffffffff;
    upper = bit64(seed) >> 32;
    z = fnv1a(fnv_hash, lower);
    w = fnv1a(fnv_hash, upper);
    jsr = fnv1a(fnv_hash, lower);
    jcong = fnv1a(fnv_hash, upper);
    for i in range(PROGPOW_REGS):
        mix_seq_dst.append(i);
        mix_seq_cache.append(i);
    result = [];
    for i in range(PROGPOW_REGS):
        result = kiss99(z, w, jsr, jcong);
        z = result[0];
        w = result[1];
        jsr = result[2];
        jcong = result[3];
        j = result[4] % (i + 1);
        tmp = swap(mix_seq_dst[i], mix_seq_dst[j]);
        mix_seq_dst[i] = tmp[0];
        mix_seq_dst[j] = tmp[1];
    
        result = kiss99(z, w, jsr, jcong);
        z = result[0];
        w = result[1];
        jsr = result[2];
        jcong = result[3];
        j = result[4] % (i + 1);
        tmp2 = swap(mix_seq_cache[i], mix_seq_cache[j]);
        mix_seq_cache[i] = tmp2[0];
        mix_seq_cache[j] = tmp2[1];
    return [mix_seq_dst, mix_seq_cache, result];

Main Loop

Now, we specify the main "hashimoto"-like loop, where we aggregate data from the full dataset in order to produce our final value for a particular header and nonce. In the code below, header represents the SHA3-256 hash of the RLP representation of a truncated block header, that is, of a header excluding the fields mixHash and nonce. nonce is the eight bytes of a 64 bit unsigned integer in big-endian order. So nonce[::-1] is the eight-byte little-endian representation of that value: The variable prog_seed is calculated by taking the current block number divided by PROGPOW_PERIOD.

def progpow_search(prog_seed, header, nonce, dag):

    # combine header+nonce into a 64 byte seed
    s = keccak_f800(header + nonce[::-1])
    # start the mix with replicated s
    # invert the byte order of the seed
    mix = fill_mix(s);

    #execute the randomly generated inner loop
    for i in range(PROGPOW_CNT_DAG):
        progPowLoop(prog_seed, i, mix, dag);

    #reduce the mix data to a single result per lane
    lane_hashes = [];
    for l in range(PROGPOW_LANES):
        lane_hashes.append(0x811c9dc5);
        for i in range(PROGPOW_REGS):
            fnv1a(lane_hash[l], mix[l * PROGPOW_REGS + i]);

    # compress lane results to single result
    result = []
    for i in range(8):
        result.append(0x811c9dc5);
    for i in range(PROGPOW_LANES):
        result[i%8] = fnv1a(result[i%8], lane_hashes[i]);

    return keccak_f800(header, seed, result);

def progPowLoop(prog_seed, loop, mix, dag):
    offset_g = mix[(loop % PROGPOW_LANES) * PROGPOW_REGS + 0];
    #4 = sizeof(uint32_t)
    offset_g = offset_g % (DAG_BYTES / (PROGPOW_LANES*PROGPOW_DAG_LOADS * 4));
    for l in range(PROGPOW_LANES):
        data_g = [];
        offset_l = offset_g * PROGPOW_LANES + (l ^ loop) % PROGPOW_LANES;
        for i in range(PROGPOW_DAG_LOADS):
            index = offset_l * PROGPOW_DAG_LOADS + i;
            data_g.append(dag[index]);
        mix_seq_dst = [];
        mix_seq_cache = [];
        mix_seq_dst_cnt = 0;
        mix_seq_cache_cnt = 0;
        tmp = progPowInit(prog_seed);
        mix_seq_dst = tmp[0];
        mix_seq_cache = tmp[1];
        prog_rnd = tmp[2];
        _max = max(PROGPOW_CNT_CACHE,PROGPOW_CNT_MATH);
        for i in range(_max):
            if i < PROGPOW_CNT_CACHE:
                mix_cache = mix_seq_cache[mix_seq_cache_cnt % PROGPOW_REGS];
                mix_seq_cache_cnt = mix_seq_cache_cnt + 1;
                offset = mix[l * PROGPOW_REGS + mix_cache]; 
                offset = offset % (PROGPOW_CACHE_BYTES / 4);
                data = dag[offset];
                mix_dst = mix_seq_dst[mix_seq_dst_cnt % PROGPOW_REGS];
                mix_seq_dst_cnt = mix_seq_dst_cnt + 1;
                prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
                merge(mix[l * PROGPOW_REGS + mix_dst], data, prog_rnd[4]);
            elif i < PROGPOW_CNT_MATH:
                prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
                mix_src_1 = prog_rnd[4] % PROGPOW_REGS;
                prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
                mix_src_2 = prog_rnd[4] % PROGPOW_REGS;
                prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
                data = math(mix[l * PROGPOW_REGS + mix_src_1], mix[l * PROGPOW_REGS + mix_src_2], prog_rnd[4]);
                prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
                mix_dst = mix_seq_dst[mix_seq_dst_cnt % PROGPOW_REGS];
                mix_seq_dst_cnt = mix_seq_dst_cnt + 1;
                merge(mix[l * PROGPOW_REGS + mix_dst], data, prog_rnd[4]);
        prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);     
        merge(mix[l* PROGPOW_REGS + 0], data_g[0], prog_rnd[4]);
        for i in range(1, PROGPOW_DAG_LOADS):
            prog_rnd = kiss99(prog_rnd[0], prog_rnd[1], prog_rnd[2], prog_rnd[3]);
            mix_dst = mix_seq_dst[mix_seq_dst_cnt % PROGPOW_REGS];
            mix_seq_dst_cnt = mix_seq_dst_cnt + 1;
            merge(mix[l* PROGPOW_REGS + mix_dst], data_g[i], prog_rnd[4]);

def progpow_search_light(prog_seed, cache, header, nonce):
    return progpow_search(prog_seed, header, nonce, lambda x: calc_dataset_item(cache, x))

def progpow_search_full(prog_seed, dataset, header, nonce):
    return progpow_search(prog_seed, header, nonce,  lambda x: dataset[x])

The flow of the overall algorithm is as following

At the beginning of the algorithm, we use a keccak to hash header and nonce of the current block to create a seed. We use this seed to generate the initial data for a 512 bytes wide "mix". We repeatedly fetch random loads from the dag and the cache, perform random math on them and use fnv1a to combine it to the mix. 256 byte wide sequential accesses are used, which increases the efficiency and reduces the overhead on modern GPU's. After that, we combine the mix into a single 256-bit value again using fnv1a. At the end, we use another keccak hash on this single 256-bit value to generate a result.

If the output of this algorithm is below the desired target, then the nonce is valid. Note that the extra application of keccak at the end ensures that there exists an intermediate nonce which can be provided to prove that at least a small amount of work was done; this quick outer PoW verification can be used for anti-DDoS purposes. It also serves to provide statistical assurance that the result is an unbiased, 256 bit number.

Mining

The mining algorithm is defined as follows:

def mine(block_number, dataset, header, difficulty):
    # zero-pad target to compare with hash on the same digit when reversed
    target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
    from random import randint
    nonce = randint(0, 2**64)
    prog_seed = block_number / PROGPOW_PERIOD;
    while progpow_search_full(prog_seed, dataset, header, nonce) > target:
        nonce = (nonce + 1) % 2**64
    return nonce

Defining the Seed Hash

In order to compute the seed hash that would be used to mine on top of a given block, we use the following algorithm:

 def get_seedhash(block):
     s = '\x00' * 32
     for i in range(block.number // EPOCH_LENGTH):
         s = serialize_hash(sha3_256(s))
     return s

Note that for smooth mining and verifying, we recommend pre-computing future seedhashes and datasets in a separate thread.

Appendix

The following code should be prepended if you are interested in running the above python spec as code.

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

def swap(x, y):
    return [y, x];

Random math

This functions are used in the random math generation

def bit64(x):
    return a & 0xffffffffffffffff;
    
def rotl(num, bits):
    bit = num & (1 << (bits-1))
    num <<= 1
    if(bit):
        num |= 1
    num &= (2**bits-1)
    return num

def rotr(num, bits):
    num &= (2**bits-1)
    bit = num & 1
    num >>= 1
    if(bit):
        num |= (1 << (bits-1))
    return num
    
def clz(x):
    if not(x):
        return 32;
    return 32 - len('{0:b}'.format(x));
    
def popcount(x):
    return bin(x).count('1')

KISS99 Lookup

The default parameters for KISS99

z = 362436069;
w = 521288629;
jsr = 123456789;
jcong = 380116160;

The following lookup table provides the first 100 results of KISS99 with the default parameters as a seed.

def get_kiss99():
    kiss = [];
    for i in range(100):
        kiss.append(kiss99());
    print kiss;

kiss = [3950301152, 1424329448L, 2656635869L, 2682398698L, 903628396L, 
1153611800L, 56390649L, 1370973434L, 520257718L, 2122453761L, 2554816484L, 
3895770088L, 3866258017L, 867473115L, 2330321561L, 3738117532L, 739492310L, 
3356986988L, 4121481619L, 1945114613L, 107859486L, 527334584L, 108036578L, 
1375747641L, 4197964130L, 49409L, 2038950561L, 2515682904L, 2559331684L, 
566635747L, 408753308L, 3157003060L, 4018187377L, 2717398973L, 1405081013L, 
800138346L, 3047868511L, 3003202702L, 3653848159L, 1064816952L, 587144236L, 
690246849L, 1909269909L, 1983165686L, 3553317884L, 387001780L, 2399255572L, 
4203030651L, 1518345267L, 2978452866L, 3785987833L, 1826175735L, 536736026L, 
2458085845L, 151606592L, 1474398657L, 2533916130L, 1799368591L, 2744766718L, 
338227066L, 1460640986L, 500826146L, 2013747780L, 3671101135L, 211318516L, 
2636015021L, 4266401009L, 476631299L, 75353176L, 676108647L, 2991494529L, 
512024433L, 1484872285L, 1702884966L, 2381801348L, 3776410001L, 3839723392L, 
3537489105L, 4170880493L, 3466523276L, 1855812766L, 1784734245L, 1614734042L, 
911088043L, 2691407282L, 2533708940L, 2116374786L, 969227938L, 500946894L, 
1860086243L, 2794734747L, 2034327762L, 572197680L, 523985329L, 2119797904L, 
712707104L, 2860043282L, 83178705L, 157293271L, 1902702629L]

Data Sizes

The following lookup tables provide approximately 2048 tabulated epochs of data sizes and cache sizes. They were generated with the Mathematica function provided here:

def get_datasize(block_number):
    return data_sizes[block_number // EPOCH_LENGTH]

def get_cachesize(block_number):
    return cache_sizes[block_number // EPOCH_LENGTH]

data_sizes = [
1073739904, 1082130304, 1090514816, 1098906752, 1107293056, 
1115684224, 1124070016, 1132461952, 1140849536, 1149232768, 
1157627776, 1166013824, 1174404736, 1182786944, 1191180416, 
1199568512, 1207958912, 1216345216, 1224732032, 1233124736, 
1241513344, 1249902464, 1258290304, 1266673792, 1275067264, 
1283453312, 1291844992, 1300234112, 1308619904, 1317010048, 
1325397376, 1333787776, 1342176128, 1350561664, 1358954368, 
1367339392, 1375731584, 1384118144, 1392507008, 1400897408, 
1409284736, 1417673344, 1426062464, 1434451072, 1442839168, 
1451229056, 1459615616, 1468006016, 1476394112, 1484782976, 
1493171584, 1501559168, 1509948032, 1518337664, 1526726528, 
1535114624, 1543503488, 1551892096, 1560278656, 1568669056, 
1577056384, 1585446272, 1593831296, 1602219392, 1610610304, 
1619000192, 1627386752, 1635773824, 1644164224, 1652555648, 
1660943488, 1669332608, 1677721216, 1686109312, 1694497664, 
1702886272, 1711274624, 1719661184, 1728047744, 1736434816, 
1744829056, 1753218944, 1761606272, 1769995904, 1778382464, 
1786772864, 1795157888, 1803550592, 1811937664, 1820327552, 
1828711552, 1837102976, 1845488768, 1853879936, 1862269312, 
1870656896, 1879048064, 1887431552, 1895825024, 1904212096, 
1912601216, 1920988544, 1929379456, 1937765504, 1946156672, 
1954543232, 1962932096, 1971321728, 1979707264, 1988093056, 
1996487552, 2004874624, 2013262208, 2021653888, 2030039936, 
2038430848, 2046819968, 2055208576, 2063596672, 2071981952, 
2080373632, 2088762752, 2097149056, 2105539712, 2113928576, 
2122315136, 2130700672, 2139092608, 2147483264, 2155872128, 
2164257664, 2172642176, 2181035392, 2189426048, 2197814912, 
2206203008, 2214587264, 2222979712, 2231367808, 2239758208, 
2248145024, 2256527744, 2264922752, 2273312128, 2281701248, 
2290086272, 2298476672, 2306867072, 2315251072, 2323639168, 
2332032128, 2340420224, 2348808064, 2357196416, 2365580416, 
2373966976, 2382363008, 2390748544, 2399139968, 2407530368, 
2415918976, 2424307328, 2432695424, 2441084288, 2449472384, 
2457861248, 2466247808, 2474637184, 2483026816, 2491414144, 
2499803776, 2508191872, 2516582272, 2524970368, 2533359232, 
2541743488, 2550134144, 2558525056, 2566913408, 2575301504, 
2583686528, 2592073856, 2600467328, 2608856192, 2617240448, 
2625631616, 2634022016, 2642407552, 2650796416, 2659188352, 
2667574912, 2675965312, 2684352896, 2692738688, 2701130624, 
2709518464, 2717907328, 2726293376, 2734685056, 2743073152, 
2751462016, 2759851648, 2768232832, 2776625536, 2785017728, 
2793401984, 2801794432, 2810182016, 2818571648, 2826959488, 
2835349376, 2843734144, 2852121472, 2860514432, 2868900992, 
2877286784, 2885676928, 2894069632, 2902451584, 2910843008, 
2919234688, 2927622784, 2936011648, 2944400768, 2952789376, 
2961177728, 2969565568, 2977951616, 2986338944, 2994731392, 
3003120256, 3011508352, 3019895936, 3028287104, 3036675968, 
3045063808, 3053452928, 3061837696, 3070228352, 3078615424, 
3087003776, 3095394944, 3103782272, 3112173184, 3120562048, 
3128944768, 3137339264, 3145725056, 3154109312, 3162505088, 
3170893184, 3179280256, 3187669376, 3196056704, 3204445568, 
3212836736, 3221224064, 3229612928, 3238002304, 3246391168, 
3254778496, 3263165824, 3271556224, 3279944576, 3288332416, 
3296719232, 3305110912, 3313500032, 3321887104, 3330273152, 
3338658944, 3347053184, 3355440512, 3363827072, 3372220288, 
3380608384, 3388997504, 3397384576, 3405774208, 3414163072, 
3422551936, 3430937984, 3439328384, 3447714176, 3456104576, 
3464493952, 3472883584, 3481268864, 3489655168, 3498048896, 
3506434432, 3514826368, 3523213952, 3531603584, 3539987072, 
3548380288, 3556763264, 3565157248, 3573545344, 3581934464, 
3590324096, 3598712704, 3607098752, 3615488384, 3623877248, 
3632265856, 3640646528, 3649043584, 3657430144, 3665821568, 
3674207872, 3682597504, 3690984832, 3699367808, 3707764352, 
3716152448, 3724541056, 3732925568, 3741318016, 3749706368, 
3758091136, 3766481536, 3774872704, 3783260032, 3791650432, 
3800036224, 3808427648, 3816815488, 3825204608, 3833592704, 
3841981568, 3850370432, 3858755968, 3867147904, 3875536256, 
3883920512, 3892313728, 3900702592, 3909087872, 3917478784, 
3925868416, 3934256512, 3942645376, 3951032192, 3959422336, 
3967809152, 3976200064, 3984588416, 3992974976, 4001363584, 
4009751168, 4018141312, 4026530432, 4034911616, 4043308928, 
4051695488, 4060084352, 4068472448, 4076862848, 4085249408, 
4093640576, 4102028416, 4110413696, 4118805632, 4127194496, 
4135583104, 4143971968, 4152360832, 4160746112, 4169135744, 
4177525888, 4185912704, 4194303616, 4202691968, 4211076736, 
4219463552, 4227855488, 4236246656, 4244633728, 4253022848, 
4261412224, 4269799808, 4278184832, 4286578048, 4294962304, 
4303349632, 4311743104, 4320130432, 4328521088, 4336909184, 
4345295488, 4353687424, 4362073472, 4370458496, 4378852736, 
4387238528, 4395630208, 4404019072, 4412407424, 4420790656, 
4429182848, 4437571456, 4445962112, 4454344064, 4462738048, 
4471119232, 4479516544, 4487904128, 4496289664, 4504682368, 
4513068416, 4521459584, 4529846144, 4538232704, 4546619776, 
4555010176, 4563402112, 4571790208, 4580174464, 4588567936, 
4596957056, 4605344896, 4613734016, 4622119808, 4630511488, 
4638898816, 4647287936, 4655675264, 4664065664, 4672451968, 
4680842624, 4689231488, 4697620352, 4706007424, 4714397056, 
4722786176, 4731173248, 4739562368, 4747951744, 4756340608, 
4764727936, 4773114496, 4781504384, 4789894784, 4798283648, 
4806667648, 4815059584, 4823449472, 4831835776, 4840226176, 
4848612224, 4857003392, 4865391488, 4873780096, 4882169728, 
4890557312, 4898946944, 4907333248, 4915722368, 4924110976, 
4932499328, 4940889728, 4949276032, 4957666432, 4966054784, 
4974438016, 4982831488, 4991221376, 4999607168, 5007998848, 
5016386432, 5024763776, 5033164672, 5041544576, 5049941888, 
5058329728, 5066717056, 5075107456, 5083494272, 5091883904, 
5100273536, 5108662144, 5117048192, 5125436032, 5133827456, 
5142215296, 5150605184, 5158993024, 5167382144, 5175769472, 
5184157568, 5192543872, 5200936064, 5209324928, 5217711232, 
5226102656, 5234490496, 5242877312, 5251263872, 5259654016, 
5268040832, 5276434304, 5284819328, 5293209728, 5301598592, 
5309986688, 5318374784, 5326764416, 5335151488, 5343542144, 
5351929472, 5360319872, 5368706944, 5377096576, 5385484928, 
5393871232, 5402263424, 5410650496, 5419040384, 5427426944, 
5435816576, 5444205952, 5452594816, 5460981376, 5469367936, 
5477760896, 5486148736, 5494536832, 5502925952, 5511315328, 
5519703424, 5528089984, 5536481152, 5544869504, 5553256064, 
5561645696, 5570032768, 5578423936, 5586811264, 5595193216, 
5603585408, 5611972736, 5620366208, 5628750464, 5637143936, 
5645528192, 5653921408, 5662310272, 5670694784, 5679082624, 
5687474048, 5695864448, 5704251008, 5712641408, 5721030272, 
5729416832, 5737806208, 5746194304, 5754583936, 5762969984, 
5771358592, 5779748224, 5788137856, 5796527488, 5804911232, 
5813300608, 5821692544, 5830082176, 5838468992, 5846855552, 
5855247488, 5863636096, 5872024448, 5880411008, 5888799872, 
5897186432, 5905576832, 5913966976, 5922352768, 5930744704, 
5939132288, 5947522432, 5955911296, 5964299392, 5972688256, 
5981074304, 5989465472, 5997851008, 6006241408, 6014627968, 
6023015552, 6031408256, 6039796096, 6048185216, 6056574848, 
6064963456, 6073351808, 6081736064, 6090128768, 6098517632, 
6106906496, 6115289216, 6123680896, 6132070016, 6140459648, 
6148849024, 6157237376, 6165624704, 6174009728, 6182403712, 
6190792064, 6199176064, 6207569792, 6215952256, 6224345216, 
6232732544, 6241124224, 6249510272, 6257899136, 6266287744, 
6274676864, 6283065728, 6291454336, 6299843456, 6308232064, 
6316620928, 6325006208, 6333395584, 6341784704, 6350174848, 
6358562176, 6366951296, 6375337856, 6383729536, 6392119168, 
6400504192, 6408895616, 6417283456, 6425673344, 6434059136, 
6442444672, 6450837376, 6459223424, 6467613056, 6476004224, 
6484393088, 6492781952, 6501170048, 6509555072, 6517947008, 
6526336384, 6534725504, 6543112832, 6551500672, 6559888768, 
6568278656, 6576662912, 6585055616, 6593443456, 6601834112, 
6610219648, 6618610304, 6626999168, 6635385472, 6643777408, 
6652164224, 6660552832, 6668941952, 6677330048, 6685719424, 
6694107776, 6702493568, 6710882176, 6719274112, 6727662976, 
6736052096, 6744437632, 6752825984, 6761213824, 6769604224, 
6777993856, 6786383488, 6794770816, 6803158144, 6811549312, 
6819937664, 6828326528, 6836706176, 6845101696, 6853491328, 
6861880448, 6870269312, 6878655104, 6887046272, 6895433344, 
6903822208, 6912212864, 6920596864, 6928988288, 6937377152, 
6945764992, 6954149248, 6962544256, 6970928768, 6979317376, 
6987709312, 6996093824, 7004487296, 7012875392, 7021258624, 
7029652352, 7038038912, 7046427776, 7054818944, 7063207808, 
7071595136, 7079980928, 7088372608, 7096759424, 7105149824, 
7113536896, 7121928064, 7130315392, 7138699648, 7147092352, 
7155479168, 7163865728, 7172249984, 7180648064, 7189036672, 
7197424768, 7205810816, 7214196608, 7222589824, 7230975104, 
7239367552, 7247755904, 7256145536, 7264533376, 7272921472, 
7281308032, 7289694848, 7298088832, 7306471808, 7314864512, 
7323253888, 7331643008, 7340029568, 7348419712, 7356808832, 
7365196672, 7373585792, 7381973888, 7390362752, 7398750592, 
7407138944, 7415528576, 7423915648, 7432302208, 7440690304, 
7449080192, 7457472128, 7465860992, 7474249088, 7482635648, 
7491023744, 7499412608, 7507803008, 7516192384, 7524579968, 
7532967296, 7541358464, 7549745792, 7558134656, 7566524032, 
7574912896, 7583300992, 7591690112, 7600075136, 7608466816, 
7616854912, 7625244544, 7633629824, 7642020992, 7650410368, 
7658794112, 7667187328, 7675574912, 7683961984, 7692349568, 
7700739712, 7709130368, 7717519232, 7725905536, 7734295424, 
7742683264, 7751069056, 7759457408, 7767849088, 7776238208, 
7784626816, 7793014912, 7801405312, 7809792128, 7818179968, 
7826571136, 7834957184, 7843347328, 7851732352, 7860124544, 
7868512384, 7876902016, 7885287808, 7893679744, 7902067072, 
7910455936, 7918844288, 7927230848, 7935622784, 7944009344, 
7952400256, 7960786048, 7969176704, 7977565312, 7985953408, 
7994339968, 8002730368, 8011119488, 8019508096, 8027896192, 
8036285056, 8044674688, 8053062272, 8061448832, 8069838464, 
8078227328, 8086616704, 8095006592, 8103393664, 8111783552, 
8120171392, 8128560256, 8136949376, 8145336704, 8153726848, 
8162114944, 8170503296, 8178891904, 8187280768, 8195669632, 
8204058496, 8212444544, 8220834176, 8229222272, 8237612672, 
8246000768, 8254389376, 8262775168, 8271167104, 8279553664, 
8287944064, 8296333184, 8304715136, 8313108352, 8321497984, 
8329885568, 8338274432, 8346663296, 8355052928, 8363441536, 
8371828352, 8380217984, 8388606592, 8396996224, 8405384576, 
8413772672, 8422161536, 8430549376, 8438939008, 8447326592, 
8455715456, 8464104832, 8472492928, 8480882048, 8489270656, 
8497659776, 8506045312, 8514434944, 8522823808, 8531208832, 
8539602304, 8547990656, 8556378752, 8564768384, 8573154176, 
8581542784, 8589933952, 8598322816, 8606705024, 8615099264, 
8623487872, 8631876992, 8640264064, 8648653952, 8657040256, 
8665430656, 8673820544, 8682209152, 8690592128, 8698977152, 
8707374464, 8715763328, 8724151424, 8732540032, 8740928384, 
8749315712, 8757704576, 8766089344, 8774480768, 8782871936, 
8791260032, 8799645824, 8808034432, 8816426368, 8824812928, 
8833199488, 8841591424, 8849976448, 8858366336, 8866757248, 
8875147136, 8883532928, 8891923328, 8900306816, 8908700288, 
8917088384, 8925478784, 8933867392, 8942250368, 8950644608, 
8959032704, 8967420544, 8975809664, 8984197504, 8992584064, 
9000976256, 9009362048, 9017752448, 9026141312, 9034530688, 
9042917504, 9051307904, 9059694208, 9068084864, 9076471424, 
9084861824, 9093250688, 9101638528, 9110027648, 9118416512, 
9126803584, 9135188096, 9143581312, 9151969664, 9160356224, 
9168747136, 9177134464, 9185525632, 9193910144, 9202302848, 
9210690688, 9219079552, 9227465344, 9235854464, 9244244864, 
9252633472, 9261021824, 9269411456, 9277799296, 9286188928, 
9294574208, 9302965888, 9311351936, 9319740032, 9328131968, 
9336516736, 9344907392, 9353296768, 9361685888, 9370074752, 
9378463616, 9386849408, 9395239808, 9403629184, 9412016512, 
9420405376, 9428795008, 9437181568, 9445570688, 9453960832, 
9462346624, 9470738048, 9479121536, 9487515008, 9495903616, 
9504289664, 9512678528, 9521067904, 9529456256, 9537843584, 
9546233728, 9554621312, 9563011456, 9571398784, 9579788672, 
9588178304, 9596567168, 9604954496, 9613343104, 9621732992, 
9630121856, 9638508416, 9646898816, 9655283584, 9663675776, 
9672061312, 9680449664, 9688840064, 9697230464, 9705617536, 
9714003584, 9722393984, 9730772608, 9739172224, 9747561088, 
9755945344, 9764338816, 9772726144, 9781116544, 9789503872, 
9797892992, 9806282624, 9814670464, 9823056512, 9831439232, 
9839833984, 9848224384, 9856613504, 9865000576, 9873391232, 
9881772416, 9890162816, 9898556288, 9906940544, 9915333248, 
9923721088, 9932108672, 9940496512, 9948888448, 9957276544, 
9965666176, 9974048384, 9982441088, 9990830464, 9999219584, 
10007602816, 10015996544, 10024385152, 10032774016, 10041163648, 
10049548928, 10057940096, 10066329472, 10074717824, 10083105152, 
10091495296, 10099878784, 10108272256, 10116660608, 10125049216, 
10133437312, 10141825664, 10150213504, 10158601088, 10166991232, 
10175378816, 10183766144, 10192157312, 10200545408, 10208935552, 
10217322112, 10225712768, 10234099328, 10242489472, 10250876032, 
10259264896, 10267656064, 10276042624, 10284429184, 10292820352, 
10301209472, 10309598848, 10317987712, 10326375296, 10334763392, 
10343153536, 10351541632, 10359930752, 10368318592, 10376707456, 
10385096576, 10393484672, 10401867136, 10410262144, 10418647424, 
10427039104, 10435425664, 10443810176, 10452203648, 10460589952, 
10468982144, 10477369472, 10485759104, 10494147712, 10502533504, 
10510923392, 10519313536, 10527702656, 10536091264, 10544478592, 
10552867712, 10561255808, 10569642368, 10578032768, 10586423168, 
10594805632, 10603200128, 10611588992, 10619976064, 10628361344, 
10636754048, 10645143424, 10653531776, 10661920384, 10670307968, 
10678696832, 10687086464, 10695475072, 10703863168, 10712246144, 
10720639616, 10729026688, 10737414784, 10745806208, 10754190976, 
10762581376, 10770971264, 10779356288, 10787747456, 10796135552, 
10804525184, 10812915584, 10821301888, 10829692288, 10838078336, 
10846469248, 10854858368, 10863247232, 10871631488, 10880023424, 
10888412032, 10896799616, 10905188992, 10913574016, 10921964672, 
10930352768, 10938742912, 10947132544, 10955518592, 10963909504, 
10972298368, 10980687488, 10989074816, 10997462912, 11005851776, 
11014241152, 11022627712, 11031017344, 11039403904, 11047793024, 
11056184704, 11064570752, 11072960896, 11081343872, 11089737856, 
11098128256, 11106514816, 11114904448, 11123293568, 11131680128, 
11140065152, 11148458368, 11156845696, 11165236864, 11173624192, 
11182013824, 11190402688, 11198790784, 11207179136, 11215568768, 
11223957376, 11232345728, 11240734592, 11249122688, 11257511296, 
11265899648, 11274285952, 11282675584, 11291065472, 11299452544, 
11307842432, 11316231296, 11324616832, 11333009024, 11341395584, 
11349782656, 11358172288, 11366560384, 11374950016, 11383339648, 
11391721856, 11400117376, 11408504192, 11416893568, 11425283456, 
11433671552, 11442061184, 11450444672, 11458837888, 11467226752, 
11475611776, 11484003968, 11492392064, 11500780672, 11509169024, 
11517550976, 11525944448, 11534335616, 11542724224, 11551111808, 
11559500672, 11567890304, 11576277376, 11584667008, 11593056128, 
11601443456, 11609830016, 11618221952, 11626607488, 11634995072, 
11643387776, 11651775104, 11660161664, 11668552576, 11676940928, 
11685330304, 11693718656, 11702106496, 11710496128, 11718882688, 
11727273088, 11735660416, 11744050048, 11752437376, 11760824704, 
11769216128, 11777604736, 11785991296, 11794381952, 11802770048, 
11811157888, 11819548544, 11827932544, 11836324736, 11844713344, 
11853100928, 11861486464, 11869879936, 11878268032, 11886656896, 
11895044992, 11903433088, 11911822976, 11920210816, 11928600448, 
11936987264, 11945375872, 11953761152, 11962151296, 11970543488, 
11978928512, 11987320448, 11995708288, 12004095104, 12012486272, 
12020875136, 12029255552, 12037652096, 12046039168, 12054429568, 
12062813824, 12071206528, 12079594624, 12087983744, 12096371072, 
12104759936, 12113147264, 12121534592, 12129924992, 12138314624, 
12146703232, 12155091584, 12163481216, 12171864704, 12180255872, 
12188643968, 12197034112, 12205424512, 12213811328, 12222199424, 
12230590336, 12238977664, 12247365248, 12255755392, 12264143488, 
12272531584, 12280920448, 12289309568, 12297694592, 12306086528, 
12314475392, 12322865024, 12331253632, 12339640448, 12348029312, 
12356418944, 12364805248, 12373196672, 12381580928, 12389969024, 
12398357632, 12406750592, 12415138432, 12423527552, 12431916416, 
12440304512, 12448692352, 12457081216, 12465467776, 12473859968, 
12482245504, 12490636672, 12499025536, 12507411584, 12515801728, 
12524190592, 12532577152, 12540966272, 12549354368, 12557743232, 
12566129536, 12574523264, 12582911872, 12591299456, 12599688064, 
12608074624, 12616463488, 12624845696, 12633239936, 12641631616, 
12650019968, 12658407296, 12666795136, 12675183232, 12683574656, 
12691960192, 12700350592, 12708740224, 12717128576, 12725515904, 
12733906816, 12742295168, 12750680192, 12759071872, 12767460736, 
12775848832, 12784236928, 12792626816, 12801014656, 12809404288, 
12817789312, 12826181504, 12834568832, 12842954624, 12851345792, 
12859732352, 12868122496, 12876512128, 12884901248, 12893289088, 
12901672832, 12910067584, 12918455168, 12926842496, 12935232896, 
12943620736, 12952009856, 12960396928, 12968786816, 12977176192, 
12985563776, 12993951104, 13002341504, 13010730368, 13019115392, 
13027506304, 13035895168, 13044272512, 13052673152, 13061062528, 
13069446272, 13077838976, 13086227072, 13094613632, 13103000192, 
13111393664, 13119782528, 13128157568, 13136559232, 13144945024, 
13153329536, 13161724288, 13170111872, 13178502784, 13186884736, 
13195279744, 13203667072, 13212057472, 13220445824, 13228832128, 
13237221248, 13245610624, 13254000512, 13262388352, 13270777472, 
13279166336, 13287553408, 13295943296, 13304331904, 13312719488, 
13321108096, 13329494656, 13337885824, 13346274944, 13354663808, 
13363051136, 13371439232, 13379825024, 13388210816, 13396605056, 
13404995456, 13413380224, 13421771392, 13430159744, 13438546048, 
13446937216, 13455326848, 13463708288, 13472103808, 13480492672, 
13488875648, 13497269888, 13505657728, 13514045312, 13522435712, 
13530824576, 13539210112, 13547599232, 13555989376, 13564379008, 
13572766336, 13581154432, 13589544832, 13597932928, 13606320512, 
13614710656, 13623097472, 13631477632, 13639874944, 13648264064, 
13656652928, 13665041792, 13673430656, 13681818496, 13690207616, 
13698595712, 13706982272, 13715373184, 13723762048, 13732150144, 
13740536704, 13748926592, 13757316224, 13765700992, 13774090112, 
13782477952, 13790869376, 13799259008, 13807647872, 13816036736, 
13824425344, 13832814208, 13841202304, 13849591424, 13857978752, 
13866368896, 13874754688, 13883145344, 13891533184, 13899919232, 
13908311168, 13916692096, 13925085056, 13933473152, 13941866368, 
13950253696, 13958643584, 13967032192, 13975417216, 13983807616, 
13992197504, 14000582272, 14008973696, 14017363072, 14025752192, 
14034137984, 14042528384, 14050918016, 14059301504, 14067691648, 
14076083584, 14084470144, 14092852352, 14101249664, 14109635968, 
14118024832, 14126407552, 14134804352, 14143188608, 14151577984, 
14159968384, 14168357248, 14176741504, 14185127296, 14193521024, 
14201911424, 14210301824, 14218685056, 14227067264, 14235467392, 
14243855488, 14252243072, 14260630144, 14269021568, 14277409408, 
14285799296, 14294187904, 14302571392, 14310961792, 14319353728, 
14327738752, 14336130944, 14344518784, 14352906368, 14361296512, 
14369685376, 14378071424, 14386462592, 14394848128, 14403230848, 
14411627392, 14420013952, 14428402304, 14436793472, 14445181568, 
14453569664, 14461959808, 14470347904, 14478737024, 14487122816, 
14495511424, 14503901824, 14512291712, 14520677504, 14529064832, 
14537456768, 14545845632, 14554234496, 14562618496, 14571011456, 
14579398784, 14587789184, 14596172672, 14604564608, 14612953984, 
14621341312, 14629724288, 14638120832, 14646503296, 14654897536, 
14663284864, 14671675264, 14680061056, 14688447616, 14696835968, 
14705228416, 14713616768, 14722003328, 14730392192, 14738784128, 
14747172736, 14755561088, 14763947648, 14772336512, 14780725376, 
14789110144, 14797499776, 14805892736, 14814276992, 14822670208, 
14831056256, 14839444352, 14847836032, 14856222848, 14864612992, 
14872997504, 14881388672, 14889775744, 14898165376, 14906553472, 
14914944896, 14923329664, 14931721856, 14940109696, 14948497024, 
14956887424, 14965276544, 14973663616, 14982053248, 14990439808, 
14998830976, 15007216768, 15015605888, 15023995264, 15032385152, 
15040768384, 15049154944, 15057549184, 15065939072, 15074328448, 
15082715008, 15091104128, 15099493504, 15107879296, 15116269184, 
15124659584, 15133042304, 15141431936, 15149824384, 15158214272, 
15166602368, 15174991232, 15183378304, 15191760512, 15200154496, 
15208542592, 15216931712, 15225323392, 15233708416, 15242098048, 
15250489216, 15258875264, 15267265408, 15275654528, 15284043136, 
15292431488, 15300819584, 15309208192, 15317596544, 15325986176, 
15334374784, 15342763648, 15351151744, 15359540608, 15367929728, 
15376318336, 15384706432, 15393092992, 15401481856, 15409869952, 
15418258816, 15426649984, 15435037568, 15443425664, 15451815296, 
15460203392, 15468589184, 15476979328, 15485369216, 15493755776, 
15502146944, 15510534272, 15518924416, 15527311232, 15535699072, 
15544089472, 15552478336, 15560866688, 15569254528, 15577642624, 
15586031488, 15594419072, 15602809472, 15611199104, 15619586432, 
15627975296, 15636364928, 15644753792, 15653141888, 15661529216, 
15669918848, 15678305152, 15686696576, 15695083136, 15703474048, 
15711861632, 15720251264, 15728636288, 15737027456, 15745417088, 
15753804928, 15762194048, 15770582656, 15778971008, 15787358336, 
15795747712, 15804132224, 15812523392, 15820909696, 15829300096, 
15837691264, 15846071936, 15854466944, 15862855808, 15871244672, 
15879634816, 15888020608, 15896409728, 15904799104, 15913185152, 
15921577088, 15929966464, 15938354816, 15946743424, 15955129472, 
15963519872, 15971907968, 15980296064, 15988684928, 15997073024, 
16005460864, 16013851264, 16022241152, 16030629248, 16039012736, 
16047406976, 16055794816, 16064181376, 16072571264, 16080957824, 
16089346688, 16097737856, 16106125184, 16114514816, 16122904192, 
16131292544, 16139678848, 16148066944, 16156453504, 16164839552, 
16173236096, 16181623424, 16190012032, 16198401152, 16206790528, 
16215177344, 16223567744, 16231956352, 16240344704, 16248731008, 
16257117824, 16265504384, 16273898624, 16282281856, 16290668672, 
16299064192, 16307449216, 16315842176, 16324230016, 16332613504, 
16341006464, 16349394304, 16357783168, 16366172288, 16374561664, 
16382951296, 16391337856, 16399726208, 16408116352, 16416505472, 
16424892032, 16433282176, 16441668224, 16450058624, 16458448768, 
16466836864, 16475224448, 16483613056, 16492001408, 16500391808, 
16508779648, 16517166976, 16525555328, 16533944192, 16542330752, 
16550719616, 16559110528, 16567497088, 16575888512, 16584274816, 
16592665472, 16601051008, 16609442944, 16617832064, 16626218624, 
16634607488, 16642996096, 16651385728, 16659773824, 16668163712, 
16676552576, 16684938112, 16693328768, 16701718144, 16710095488, 
16718492288, 16726883968, 16735272832, 16743661184, 16752049792, 
16760436608, 16768827008, 16777214336, 16785599104, 16793992832, 
16802381696, 16810768768, 16819151744, 16827542656, 16835934848, 
16844323712, 16852711552, 16861101952, 16869489536, 16877876864, 
16886265728, 16894653056, 16903044736, 16911431296, 16919821696, 
16928207488, 16936592768, 16944987776, 16953375616, 16961763968, 
16970152832, 16978540928, 16986929536, 16995319168, 17003704448, 
17012096896, 17020481152, 17028870784, 17037262208, 17045649536, 
17054039936, 17062426496, 17070814336, 17079205504, 17087592064, 
17095978112, 17104369024, 17112759424, 17121147776, 17129536384, 
17137926016, 17146314368, 17154700928, 17163089792, 17171480192, 
17179864192, 17188256896, 17196644992, 17205033856, 17213423488, 
17221811072, 17230198912, 17238588032, 17246976896, 17255360384, 
17263754624, 17272143232, 17280530048, 17288918912, 17297309312, 
17305696384, 17314085504, 17322475136, 17330863744, 17339252096, 
17347640192, 17356026496, 17364413824, 17372796544, 17381190016, 
17389583488, 17397972608, 17406360704, 17414748544, 17423135872, 
17431527296, 17439915904, 17448303232, 17456691584, 17465081728, 
17473468288, 17481857408, 17490247552, 17498635904, 17507022464, 
17515409024, 17523801728, 17532189824, 17540577664, 17548966016, 
17557353344, 17565741184, 17574131584, 17582519168, 17590907008, 
17599296128, 17607687808, 17616076672, 17624455808, 17632852352, 
17641238656, 17649630848, 17658018944, 17666403968, 17674794112, 
17683178368, 17691573376, 17699962496, 17708350592, 17716739968, 
17725126528, 17733517184, 17741898112, 17750293888, 17758673024, 
17767070336, 17775458432, 17783848832, 17792236928, 17800625536, 
17809012352, 17817402752, 17825785984, 17834178944, 17842563968, 
17850955648, 17859344512, 17867732864, 17876119424, 17884511872, 
17892900224, 17901287296, 17909677696, 17918058112, 17926451072, 
17934843776, 17943230848, 17951609216, 17960008576, 17968397696, 
17976784256, 17985175424, 17993564032, 18001952128, 18010339712, 
18018728576, 18027116672, 18035503232, 18043894144, 18052283264, 
18060672128, 18069056384, 18077449856, 18085837184, 18094225792, 
18102613376, 18111004544, 18119388544, 18127781248, 18136170368, 
18144558976, 18152947328, 18161336192, 18169724288, 18178108544, 
18186498944, 18194886784, 18203275648, 18211666048, 18220048768, 
18228444544, 18236833408, 18245220736]

cache_sizes = [
16776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072, 
17693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088, 
18611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208, 
19529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968, 
20446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216, 
21364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104, 
22281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096, 
23198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112, 
24116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488, 
25034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096, 
25951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472, 
26869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744, 
27786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504, 
28700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752, 
29621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976, 
30538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248, 
31456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392, 
32372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768, 
33289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992, 
34208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984, 
35127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976, 
36044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656, 
36961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904, 
37879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672, 
38795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632, 
39713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032, 
40631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304, 
41547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912, 
42467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696, 
43382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432, 
44302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448, 
45219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208, 
46136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328, 
47053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936, 
47971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312, 
48889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712, 
49807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472, 
50724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848, 
51641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968, 
52557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576, 
53475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744, 
54394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248, 
55312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856, 
56228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488, 
57146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632, 
58064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984, 
58981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512, 
59897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968, 
60817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752, 
61733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512, 
62651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656, 
63569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392, 
64486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792, 
65402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296, 
66321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672, 
67239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304, 
68157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912, 
69074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184, 
69989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816, 
70907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168, 
71826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568, 
72744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944, 
73662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832, 
74579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544, 
75497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072, 
76414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832, 
77331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336, 
78249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664, 
79166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472, 
80084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848, 
81002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304, 
81919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984, 
82835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464, 
83753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608, 
84672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496, 
85589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112, 
86506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632, 
87424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264, 
88341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384, 
89259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376, 
90177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776, 
91093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384, 
92012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912, 
92926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136, 
93845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896, 
94764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016, 
95681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544, 
96599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536, 
97517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168, 
98434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928, 
99352384, 99482816, 99614272, 99745472, 99876416, 100007104, 
100138048, 100267072, 100401088, 100529984, 100662592, 100791872, 
100925248, 101056064, 101187392, 101317952, 101449408, 101580608, 
101711296, 101841728, 101973824, 102104896, 102235712, 102366016, 
102498112, 102628672, 102760384, 102890432, 103021888, 103153472, 
103284032, 103415744, 103545152, 103677248, 103808576, 103939648, 
104070976, 104201792, 104332736, 104462528, 104594752, 104725952, 
104854592, 104988608, 105118912, 105247808, 105381184, 105511232, 
105643072, 105774784, 105903296, 106037056, 106167872, 106298944, 
106429504, 106561472, 106691392, 106822592, 106954304, 107085376, 
107216576, 107346368, 107478464, 107609792, 107739712, 107872192, 
108003136, 108131392, 108265408, 108396224, 108527168, 108657344, 
108789568, 108920384, 109049792, 109182272, 109312576, 109444928, 
109572928, 109706944, 109837888, 109969088, 110099648, 110230976, 
110362432, 110492992, 110624704, 110755264, 110886208, 111017408, 
111148864, 111279296, 111410752, 111541952, 111673024, 111803456, 
111933632, 112066496, 112196416, 112328512, 112457792, 112590784, 
112715968, 112852672, 112983616, 113114944, 113244224, 113376448, 
113505472, 113639104, 113770304, 113901376, 114031552, 114163264, 
114294592, 114425536, 114556864, 114687424, 114818624, 114948544, 
115080512, 115212224, 115343296, 115473472, 115605184, 115736128, 
115867072, 115997248, 116128576, 116260288, 116391488, 116522944, 
116652992, 116784704, 116915648, 117046208, 117178304, 117308608, 
117440192, 117569728, 117701824, 117833024, 117964096, 118094656, 
118225984, 118357312, 118489024, 118617536, 118749632, 118882112, 
119012416, 119144384, 119275328, 119406016, 119537344, 119668672, 
119798464, 119928896, 120061376, 120192832, 120321728, 120454336, 
120584512, 120716608, 120848192, 120979136, 121109056, 121241408, 
121372352, 121502912, 121634752, 121764416, 121895744, 122027072, 
122157632, 122289088, 122421184, 122550592, 122682944, 122813888, 
122945344, 123075776, 123207488, 123338048, 123468736, 123600704, 
123731264, 123861952, 123993664, 124124608, 124256192, 124386368, 
124518208, 124649024, 124778048, 124911296, 125041088, 125173696, 
125303744, 125432896, 125566912, 125696576, 125829056, 125958592, 
126090304, 126221248, 126352832, 126483776, 126615232, 126746432, 
126876608, 127008704, 127139392, 127270336, 127401152, 127532224, 
127663552, 127794752, 127925696, 128055232, 128188096, 128319424, 
128449856, 128581312, 128712256, 128843584, 128973632, 129103808, 
129236288, 129365696, 129498944, 129629888, 129760832, 129892288, 
130023104, 130154048, 130283968, 130416448, 130547008, 130678336, 
130807616, 130939456, 131071552, 131202112, 131331776, 131464384, 
131594048, 131727296, 131858368, 131987392, 132120256, 132250816, 
132382528, 132513728, 132644672, 132774976, 132905792, 133038016, 
133168832, 133299392, 133429312, 133562048, 133692992, 133823296, 
133954624, 134086336, 134217152, 134348608, 134479808, 134607296, 
134741056, 134872384, 135002944, 135134144, 135265472, 135396544, 
135527872, 135659072, 135787712, 135921472, 136052416, 136182848, 
136313792, 136444864, 136576448, 136707904, 136837952, 136970048, 
137099584, 137232064, 137363392, 137494208, 137625536, 137755712, 
137887424, 138018368, 138149824, 138280256, 138411584, 138539584, 
138672832, 138804928, 138936128, 139066688, 139196864, 139328704, 
139460032, 139590208, 139721024, 139852864, 139984576, 140115776, 
140245696, 140376512, 140508352, 140640064, 140769856, 140902336, 
141032768, 141162688, 141294016, 141426496, 141556544, 141687488, 
141819584, 141949888, 142080448, 142212544, 142342336, 142474432, 
142606144, 142736192, 142868288, 142997824, 143129408, 143258944, 
143392448, 143523136, 143653696, 143785024, 143916992, 144045632, 
144177856, 144309184, 144440768, 144570688, 144701888, 144832448, 
144965056, 145096384, 145227584, 145358656, 145489856, 145620928, 
145751488, 145883072, 146011456, 146144704, 146275264, 146407232, 
146538176, 146668736, 146800448, 146931392, 147062336, 147193664, 
147324224, 147455936, 147586624, 147717056, 147848768, 147979456, 
148110784, 148242368, 148373312, 148503232, 148635584, 148766144, 
148897088, 149028416, 149159488, 149290688, 149420224, 149551552, 
149683136, 149814976, 149943616, 150076352, 150208064, 150338624, 
150470464, 150600256, 150732224, 150862784, 150993088, 151125952, 
151254976, 151388096, 151519168, 151649728, 151778752, 151911104, 
152042944, 152174144, 152304704, 152435648, 152567488, 152698816, 
152828992, 152960576, 153091648, 153222976, 153353792, 153484096, 
153616192, 153747008, 153878336, 154008256, 154139968, 154270912, 
154402624, 154533824, 154663616, 154795712, 154926272, 155057984, 
155188928, 155319872, 155450816, 155580608, 155712064, 155843392, 
155971136, 156106688, 156237376, 156367424, 156499264, 156630976, 
156761536, 156892352, 157024064, 157155008, 157284416, 157415872, 
157545536, 157677248, 157810496, 157938112, 158071744, 158203328, 
158334656, 158464832, 158596288, 158727616, 158858048, 158988992, 
159121216, 159252416, 159381568, 159513152, 159645632, 159776192, 
159906496, 160038464, 160169536, 160300352, 160430656, 160563008, 
160693952, 160822208, 160956352, 161086784, 161217344, 161349184, 
161480512, 161611456, 161742272, 161873216, 162002752, 162135872, 
162266432, 162397888, 162529216, 162660032, 162790976, 162922048, 
163052096, 163184576, 163314752, 163446592, 163577408, 163707968, 
163839296, 163969984, 164100928, 164233024, 164364224, 164494912, 
164625856, 164756672, 164887616, 165019072, 165150016, 165280064, 
165412672, 165543104, 165674944, 165805888, 165936832, 166067648, 
166198336, 166330048, 166461248, 166591552, 166722496, 166854208, 
166985408, 167116736, 167246656, 167378368, 167508416, 167641024, 
167771584, 167903168, 168034112, 168164032, 168295744, 168427456, 
168557632, 168688448, 168819136, 168951616, 169082176, 169213504, 
169344832, 169475648, 169605952, 169738048, 169866304, 169999552, 
170131264, 170262464, 170393536, 170524352, 170655424, 170782016, 
170917696, 171048896, 171179072, 171310784, 171439936, 171573184, 
171702976, 171835072, 171966272, 172097216, 172228288, 172359232, 
172489664, 172621376, 172747712, 172883264, 173014208, 173144512, 
173275072, 173407424, 173539136, 173669696, 173800768, 173931712, 
174063424, 174193472, 174325696, 174455744, 174586816, 174718912, 
174849728, 174977728, 175109696, 175242688, 175374272, 175504832, 
175636288, 175765696, 175898432, 176028992, 176159936, 176291264, 
176422592, 176552512, 176684864, 176815424, 176946496, 177076544, 
177209152, 177340096, 177470528, 177600704, 177731648, 177864256, 
177994816, 178126528, 178257472, 178387648, 178518464, 178650176, 
178781888, 178912064, 179044288, 179174848, 179305024, 179436736, 
179568448, 179698496, 179830208, 179960512, 180092608, 180223808, 
180354752, 180485696, 180617152, 180748096, 180877504, 181009984, 
181139264, 181272512, 181402688, 181532608, 181663168, 181795136, 
181926592, 182057536, 182190016, 182320192, 182451904, 182582336, 
182713792, 182843072, 182976064, 183107264, 183237056, 183368384, 
183494848, 183631424, 183762752, 183893824, 184024768, 184154816, 
184286656, 184417984, 184548928, 184680128, 184810816, 184941248, 
185072704, 185203904, 185335616, 185465408, 185596352, 185727296, 
185859904, 185989696, 186121664, 186252992, 186383552, 186514112, 
186645952, 186777152, 186907328, 187037504, 187170112, 187301824, 
187429184, 187562048, 187693504, 187825472, 187957184, 188087104, 
188218304, 188349376, 188481344, 188609728, 188743616, 188874304, 
189005248, 189136448, 189265088, 189396544, 189528128, 189660992, 
189791936, 189923264, 190054208, 190182848, 190315072, 190447424, 
190577984, 190709312, 190840768, 190971328, 191102656, 191233472, 
191364032, 191495872, 191626816, 191758016, 191888192, 192020288, 
192148928, 192282176, 192413504, 192542528, 192674752, 192805952, 
192937792, 193068608, 193198912, 193330496, 193462208, 193592384, 
193723456, 193854272, 193985984, 194116672, 194247232, 194379712, 
194508352, 194641856, 194772544, 194900672, 195035072, 195166016, 
195296704, 195428032, 195558592, 195690304, 195818176, 195952576, 
196083392, 196214336, 196345792, 196476736, 196607552, 196739008, 
196869952, 197000768, 197130688, 197262784, 197394368, 197523904, 
197656384, 197787584, 197916608, 198049472, 198180544, 198310208, 
198442432, 198573632, 198705088, 198834368, 198967232, 199097792, 
199228352, 199360192, 199491392, 199621696, 199751744, 199883968, 
200014016, 200146624, 200276672, 200408128, 200540096, 200671168, 
200801984, 200933312, 201062464, 201194944, 201326144, 201457472, 
201588544, 201719744, 201850816, 201981632, 202111552, 202244032, 
202374464, 202505152, 202636352, 202767808, 202898368, 203030336, 
203159872, 203292608, 203423296, 203553472, 203685824, 203816896, 
203947712, 204078272, 204208192, 204341056, 204472256, 204603328, 
204733888, 204864448, 204996544, 205125568, 205258304, 205388864, 
205517632, 205650112, 205782208, 205913536, 206044736, 206176192, 
206307008, 206434496, 206569024, 206700224, 206831168, 206961856, 
207093056, 207223616, 207355328, 207486784, 207616832, 207749056, 
207879104, 208010048, 208141888, 208273216, 208404032, 208534336, 
208666048, 208796864, 208927424, 209059264, 209189824, 209321792, 
209451584, 209582656, 209715136, 209845568, 209976896, 210106432, 
210239296, 210370112, 210501568, 210630976, 210763712, 210894272, 
211024832, 211156672, 211287616, 211418176, 211549376, 211679296, 
211812032, 211942592, 212074432, 212204864, 212334016, 212467648, 
212597824, 212727616, 212860352, 212991424, 213120832, 213253952, 
213385024, 213515584, 213645632, 213777728, 213909184, 214040128, 
214170688, 214302656, 214433728, 214564544, 214695232, 214826048, 
214956992, 215089088, 215219776, 215350592, 215482304, 215613248, 
215743552, 215874752, 216005312, 216137024, 216267328, 216399296, 
216530752, 216661696, 216790592, 216923968, 217054528, 217183168, 
217316672, 217448128, 217579072, 217709504, 217838912, 217972672, 
218102848, 218233024, 218364736, 218496832, 218627776, 218759104, 
218888896, 219021248, 219151936, 219281728, 219413056, 219545024, 
219675968, 219807296, 219938624, 220069312, 220200128, 220331456, 
220461632, 220592704, 220725184, 220855744, 220987072, 221117888, 
221249216, 221378368, 221510336, 221642048, 221772736, 221904832, 
222031808, 222166976, 222297536, 222428992, 222559936, 222690368, 
222820672, 222953152, 223083968, 223213376, 223345984, 223476928, 
223608512, 223738688, 223869376, 224001472, 224132672, 224262848, 
224394944, 224524864, 224657344, 224788288, 224919488, 225050432, 
225181504, 225312704, 225443776, 225574592, 225704768, 225834176, 
225966784, 226097216, 226229824, 226360384, 226491712, 226623424, 
226754368, 226885312, 227015104, 227147456, 227278528, 227409472, 
227539904, 227669696, 227802944, 227932352, 228065216, 228196288, 
228326464, 228457792, 228588736, 228720064, 228850112, 228981056, 
229113152, 229243328, 229375936, 229505344, 229636928, 229769152, 
229894976, 230030272, 230162368, 230292416, 230424512, 230553152, 
230684864, 230816704, 230948416, 231079616, 231210944, 231342016, 
231472448, 231603776, 231733952, 231866176, 231996736, 232127296, 
232259392, 232388672, 232521664, 232652608, 232782272, 232914496, 
233043904, 233175616, 233306816, 233438528, 233569984, 233699776, 
233830592, 233962688, 234092224, 234221888, 234353984, 234485312, 
234618304, 234749888, 234880832, 235011776, 235142464, 235274048, 
235403456, 235535936, 235667392, 235797568, 235928768, 236057152, 
236190272, 236322752, 236453312, 236583616, 236715712, 236846528, 
236976448, 237108544, 237239104, 237371072, 237501632, 237630784, 
237764416, 237895232, 238026688, 238157632, 238286912, 238419392, 
238548032, 238681024, 238812608, 238941632, 239075008, 239206336, 
239335232, 239466944, 239599168, 239730496, 239861312, 239992384, 
240122816, 240254656, 240385856, 240516928, 240647872, 240779072, 
240909632, 241040704, 241171904, 241302848, 241433408, 241565248, 
241696192, 241825984, 241958848, 242088256, 242220224, 242352064, 
242481856, 242611648, 242744896, 242876224, 243005632, 243138496, 
243268672, 243400384, 243531712, 243662656, 243793856, 243924544, 
244054592, 244187072, 244316608, 244448704, 244580032, 244710976, 
244841536, 244972864, 245104448, 245233984, 245365312, 245497792, 
245628736, 245759936, 245889856, 246021056, 246152512, 246284224, 
246415168, 246545344, 246675904, 246808384, 246939584, 247070144, 
247199552, 247331648, 247463872, 247593536, 247726016, 247857088, 
247987648, 248116928, 248249536, 248380736, 248512064, 248643008, 
248773312, 248901056, 249036608, 249167552, 249298624, 249429184, 
249560512, 249692096, 249822784, 249954112, 250085312, 250215488, 
250345792, 250478528, 250608704, 250739264, 250870976, 251002816, 
251133632, 251263552, 251395136, 251523904, 251657792, 251789248, 
251919424, 252051392, 252182464, 252313408, 252444224, 252575552, 
252706624, 252836032, 252968512, 253099712, 253227584, 253361728, 
253493056, 253623488, 253754432, 253885504, 254017216, 254148032, 
254279488, 254410432, 254541376, 254672576, 254803264, 254933824, 
255065792, 255196736, 255326528, 255458752, 255589952, 255721408, 
255851072, 255983296, 256114624, 256244416, 256374208, 256507712, 
256636096, 256768832, 256900544, 257031616, 257162176, 257294272, 
257424448, 257555776, 257686976, 257818432, 257949632, 258079552, 
258211136, 258342464, 258473408, 258603712, 258734656, 258867008, 
258996544, 259127744, 259260224, 259391296, 259522112, 259651904, 
259784384, 259915328, 260045888, 260175424, 260308544, 260438336, 
260570944, 260700992, 260832448, 260963776, 261092672, 261226304, 
261356864, 261487936, 261619648, 261750592, 261879872, 262011968, 
262143424, 262274752, 262404416, 262537024, 262667968, 262799296, 
262928704, 263061184, 263191744, 263322944, 263454656, 263585216, 
263716672, 263847872, 263978944, 264108608, 264241088, 264371648, 
264501184, 264632768, 264764096, 264895936, 265024576, 265158464, 
265287488, 265418432, 265550528, 265681216, 265813312, 265943488, 
266075968, 266206144, 266337728, 266468032, 266600384, 266731072, 
266862272, 266993344, 267124288, 267255616, 267386432, 267516992, 
267648704, 267777728, 267910592, 268040512, 268172096, 268302784, 
268435264, 268566208, 268696256, 268828096, 268959296, 269090368, 
269221312, 269352256, 269482688, 269614784, 269745856, 269876416, 
270007616, 270139328, 270270272, 270401216, 270531904, 270663616, 
270791744, 270924736, 271056832, 271186112, 271317184, 271449536, 
271580992, 271711936, 271843136, 271973056, 272105408, 272236352, 
272367296, 272498368, 272629568, 272759488, 272891456, 273022784, 
273153856, 273284672, 273415616, 273547072, 273677632, 273808448, 
273937088, 274071488, 274200896, 274332992, 274463296, 274595392, 
274726208, 274857536, 274988992, 275118656, 275250496, 275382208, 
275513024, 275643968, 275775296, 275906368, 276037184, 276167872, 
276297664, 276429376, 276560576, 276692672, 276822976, 276955072, 
277085632, 277216832, 277347008, 277478848, 277609664, 277740992, 
277868608, 278002624, 278134336, 278265536, 278395328, 278526784, 
278657728, 278789824, 278921152, 279052096, 279182912, 279313088, 
279443776, 279576256, 279706048, 279838528, 279969728, 280099648, 
280230976, 280361408, 280493632, 280622528, 280755392, 280887104, 
281018176, 281147968, 281278912, 281411392, 281542592, 281673152, 
281803712, 281935552, 282066496, 282197312, 282329024, 282458816, 
282590272, 282720832, 282853184, 282983744, 283115072, 283246144, 
283377344, 283508416, 283639744, 283770304, 283901504, 284032576, 
284163136, 284294848, 284426176, 284556992, 284687296, 284819264, 
284950208, 285081536]