Introduction

It's been more than 20 minutes since the negligent waiter has taken your order for the house special prime tofu steak with a side of chili fries.

Out of boredom, you start fiddling around with the condiments tray. To be efficient, you want to be familiar with the choice of sauces and spices before your order is finally served.

You also examine the toothpick holder and try to analyze its inner workings when - yikes - the holder's lid falls off and all 23 picks lay scattered on the table.

Being a good and hygiene oriented citizen, you decide not to just put them back in the holder. Instead of letting all the good wood go to waste, you start playing around with the picks.

In the first "round", you lay down one toothpick vertically. You've used a total of one toothpick.

In the second "round", at each end of the first toothpick, you add a perpendicular toothpick at its center point. You added two additional toothpicks for a total of three toothpicks.

In the next rounds, you continue to add perpendicular toothpicks to each free end of toothpicks already on the table.

With your 23 toothpicks, you can complete a total of six rounds:


You wonder if you'd be able to implement this sequence in your favorite programming language. Because your food still hasn't arrived, you decide to take out your laptop and start implementing...

Challenge
Implement a script that returns the amount of toothpicks needed to complete n amount of rounds of the toothpick sequence.

```
0 <= n <= 5000
```

Hint
You can attempt this brute force or get some inspiration from the math department.

Difficulty: introductory

Starter code:

def toothpick(n):
	

Solutions:
from math import log2

def t(n):
    if n == 0:
        return 0
    k = int(log2(n))
    i = n - 2**k
    if i == 0:
        return (2**(2*k+1)+1) // 3
    else:
        return t(2**k) + 2*t(i) + t(i+1) - 1

toothpick = t

from functools import lru_cache

msb = lru_cache(maxsize=None)(lambda n: 1 << n.bit_length() - 1)

# Taken from https://oeis.org/A139250
# With some upgrades cause why not?
@lru_cache(maxsize=None)
def toothpick(n):
    if n == 0: return 0
    x = msb(n)
    res = ((x**2 << 1) + 1) // 3
    if n != x:
        res += (toothpick(n - x) << 1) + toothpick(n - x + 1) - 1
    return res

# https://www.youtube.com/watch?v=_UtCli1SgjI

def toothpick(N): 
    if N <= 0: return 0
    n = 1 << (N.bit_length() - 1)
    i = N - n
    
    return toothpick(n) + 2 * toothpick(i) + toothpick(i+1) - 1 if i else (2 * n**2 + 1) / 3

import requests

r = requests.get('https://oeis.org/A139250/b139250.txt').text.splitlines()

def toothpick(n):
    return int(r[n].split()[1])

v=[0,1,3,7,11,15,23,35,43,47,55,67,79,95,123,155,171,175,183,195,207,223,251,283,303,319,347,383,423,483,571,651,683,687,695,707,719,735,763,795,815,831,859,895,935,995,1083,1163,1199,1215,1243,1279,1319,1379,1467,1551,1607,1667,1759,1871,2011,2219,2475,2667,2731,2735,2743,2755,2767,2783,2811,2843,2863,2879,2907,2943,2983,3043,3131,3211,3247,3263,3291,3327,3367,3427,3515,3599,3655,3715,3807,3919,4059,4267,4523,4715,4783,4799,4827,4863,4903,4963,5051,5135,5191,5251,5343,5455,5595,5803,6059,6255,6343,6403,6495,6607,6747,6955,7215,7439,7611,7823,8119,8483,8971,9643,10347,10795,10923,10927,10935,10947,10959,10975,11003,11035,11055,11071,11099,11135,11175,11235,11323,11403,11439,11455,11483,11519,11559,11619,11707,11791,11847,11907,11999,12111,12251,12459,12715,12907,12975,12991,13019,13055,13095,13155,13243,13327,13383,13443,13535,13647,13787,13995,14251,14447,14535,14595,14687,14799,14939,15147,15407,15631,15803,16015,16311,16675,17163,17835,18539,18987,19119,19135,19163,19199,19239,19299,19387,19471,19527,19587,19679,19791,19931,20139,20395,20591,20679,20739,20831,20943,21083,21291,21551,21775,21947,22159,22455,22819,23307,23979,24683,25135,25287,25347,25439,25551,25691,25899,26159,26383,26555,26767,27063,27427,27915,28587,29295,29775,30011,30223,30519,30883,31371,32047,32791,33411,33967,34687,35643,36859,38507,40555,42411,43435,43691,43695,43703,43715,43727,43743,43771,43803,43823,43839,43867,43903,43943,44003,44091,44171,44207,44223,44251,44287,44327,44387,44475,44559,44615,44675,44767,44879,45019,45227,45483,45675,45743,45759,45787,45823,45863,45923,46011,46095,46151,46211,46303,46415,46555,46763,47019,47215,47303,47363,47455,47567,47707,47915,48175,48399,48571,48783,49079,49443,49931,50603,51307,51755,51887,51903,51931,51967,52007,52067,52155,52239,52295,52355,52447,52559,52699,52907,53163,53359,53447,53507,53599,53711,53851,54059,54319,54543,54715,54927,55223,55587,56075,56747,57451,57903,58055,58115,58207,58319,58459,58667,58927,59151,59323,59535,59831,60195,60683,61355,62063,62543,62779,62991,63287,63651,64139,64815,65559,66179,66735,67455,68411,69627,71275,73323,75179,76203,76463,76479,76507,76543,76583,76643,76731,76815,76871,76931,77023,77135,77275,77483,77739,77935,78023,78083,78175,78287,78427,78635,78895,79119,79291,79503,79799,80163,80651,81323,82027,82479,82631,82691,82783,82895,83035,83243,83503,83727,83899,84111,84407,84771,85259,85931,86639,87119,87355,87567,87863,88227,88715,89391,90135,90755,91311,92031,92987,94203,95851,97899,99755,100783,101063,101123,101215,101327,101467,101675,101935,102159,102331,102543,102839,103203,103691,104363,105071,105551,105787,105999,106295,106659,107147,107823,108567,109187,109743,110463,111419,112635,114283,116331,118191,119247,119611,119823,120119,120483,120971,121647,122391,123011,123567,124287,125243,126459,128107,130159,132055,133251,133935,134655,135611,136827,138479,140575,142683,144479,146311,148707,151835,155915,161259,167211,171947,174251,174763,174767,174775,174787,174799,174815,174843,174875,174895,174911,174939,174975,175015,175075,175163,175243,175279,175295,175323,175359,175399,175459,175547,175631,175687,175747,175839,175951,176091,176299,176555,176747,176815,176831,176859,176895,176935,176995,177083,177167,177223,177283,177375,177487,177627,177835,178091,178287,178375,178435,178527,178639,178779,178987,179247,179471,179643,179855,180151,180515,181003,181675,182379,182827,182959,182975,183003,183039,183079,183139,183227,183311,183367,183427,183519,183631,183771,183979,184235,184431,184519,184579,184671,184783,184923,185131,185391,185615,185787,185999,186295,186659,187147,187819,188523,188975,189127,189187,189279,189391,189531,189739,189999,190223,190395,190607,190903,191267,191755,192427,193135,193615,193851,194063,194359,194723,195211,195887,196631,197251,197807,198527,199483,200699,202347,204395,206251,207275,207535,207551,207579,207615,207655,207715,207803,207887,207943,208003,208095,208207,208347,208555,208811,209007,209095,209155,209247,209359,209499,209707,209967,210191,210363,210575,210871,211235,211723,212395,213099,213551,213703,213763,213855,213967,214107,214315,214575,214799,214971,215183,215479,215843,216331,217003,217711,218191,218427,218639,218935,219299,219787,220463,221207,221827,222383,223103,224059,225275,226923,228971,230827,231855,232135,232195,232287,232399,232539,232747,233007,233231,233403,233615,233911,234275,234763,235435,236143,236623,236859,237071,237367,237731,238219,238895,239639,240259,240815,241535,242491,243707,245355,247403,249263,250319,250683,250895,251191,251555,252043,252719,253463,254083,254639,255359,256315,257531,259179,261231,263127,264323,265007,265727,266683,267899,269551,271647,273755,275551,277383,279779,282907,286987,292331,298283,303019,305323,305839,305855,305883,305919,305959,306019,306107,306191,306247,306307,306399,306511,306651,306859,307115,307311,307399,307459,307551,307663,307803,308011,308271,308495,308667,308879,309175,309539,310027,310699,311403,311855,312007,312067,312159,312271,312411,312619,312879,313103,313275,313487,313783,314147,314635,315307,316015,316495,316731,316943,317239,317603,318091,318767,319511,320131,320687,321407,322363,323579,325227,327275,329131,330159,330439,330499,330591,330703,330843,331051,331311,331535,331707,331919,332215,332579,333067,333739,334447,334927,335163,335375,335671,336035,336523,337199,337943,338563,339119,339839,340795,342011,343659,345707,347567,348623,348987,349199,349495,349859,350347,351023,351767,352387,352943,353663,354619,355835,357483,359535,361431,362627,363311,364031,364987,366203,367855,369951,372059,373855,375687,378083,381211,385291,390635,396587,401323,403631,404167,404227,404319,404431,404571,404779,405039,405263,405435,405647,405943,406307,406795,407467,408175,408655,408891,409103,409399,409763,410251,410927,411671,412291,412847,413567,414523,415739,417387,419435,421295,422351,422715,422927,423223,423587,424075,424751,425495,426115,426671,427391,428347,429563,431211,433263,435159,436355,437039,437759,438715,439931,441583,443679,445787,447583,449415,451811,454939,459019,464363,470315,475055,477391,478011,478223,478519,478883,479371,480047,480791,481411,481967,482687,483643,484859,486507,488559,490455,491651,492335,493055,494011,495227,496879,498975,501083,502879,504711,507107,510235,514315,519659,525615,530391,532867,533807,534527,535483,536699,538351,540447,542555,544351,546183,548579,551707,555787,561135,567135,572123,575199,577287,579683,582811,586895,592295,598595,604607,610031,616091,624011,634347,647851,664491,681131,692907,698027,699051,699055,699063,699075,699087,699103,699131,699163,699183,699199,699227,699263,699303,699363,699451,699531,699567,699583,699611,699647,699687,699747,699835,699919,699975,700035,700127,700239,700379,700587,700843,701035,701103,701119,701147,701183,701223,701283,701371,701455,701511,701571,701663,701775,701915,702123,702379,702575,702663,702723,702815,702927,703067,703275,703535,703759,703931,704143,704439,704803,705291,705963,706667,707115,707247,707263,707291,707327,707367,707427,707515,707599,707655,707715,707807,707919,708059,708267,708523,708719,708807,708867,708959,709071,709211,709419,709679,709903,710075,710287,710583,710947,711435,712107,712811,713263,713415,713475,713567,713679,713819,714027,714287,714511,714683,714895,715191,715555,716043,716715,717423,717903,718139,718351,718647,719011,719499,720175,720919,721539,722095,722815,723771,724987,726635,728683,730539,731563,731823,731839,731867,731903,731943,732003,732091,732175,732231,732291,732383,732495,732635,732843,733099,733295,733383,733443,733535,733647,733787,733995,734255,734479,734651,734863,735159,735523,736011,736683,737387,737839,737991,738051,738143,738255,738395,738603,738863,739087,739259,739471,739767,740131,740619,741291,741999,742479,742715,742927,743223,743587,744075,744751,745495,746115,746671,747391,748347,749563,751211,753259,755115,756143,756423,756483,756575,756687,756827,757035,757295,757519,757691,757903,758199,758563,759051,759723,760431,760911,761147,761359,761655,762019,762507,763183,763927,764547,765103,765823,766779,767995,769643,771691,773551,774607,774971,775183,775479,775843,776331,777007,777751,778371,778927,779647,780603,781819,783467,785519,787415,788611,789295,790015,790971,792187,793839,795935,798043,799839,801671,804067,807195,811275,816619,822571,827307,829611,830127,830143,830171,830207,830247,830307,830395,830479,830535,830595,830687,830799,830939,831147,831403,831599,831687,831747,831839,831951,832091,832299,832559,832783,832955,833167,833463,833827,834315,834987,835691,836143,836295,836355,836447,836559,836699,836907,837167,837391,837563,837775,838071,838435,838923,839595,840303,840783,841019,841231,841527,841891,842379,843055,843799,844419,844975,845695,846651,847867,849515,851563,853419,854447,854727,854787,854879,854991,855131,855339,855599,855823,855995,856207,856503,856867,857355,858027,858735,859215,859451,859663,859959,860323,860811,861487,862231,862851,863407,864127,865083,866299,867947,869995,871855,872911,873275,873487,873783,874147,874635,875311,876055,876675,877231,877951,878907,880123,881771,883823,885719,886915,887599,888319,889275,890491,892143,894239,896347,898143,899975,902371,905499,909579,914923,920875,925611,927919,928455,928515,928607,928719,928859,929067,929327,929551,929723,929935,930231,930595,931083,931755,932463,932943,933179,933391,933687,934051,934539,935215,935959,936579,937135,937855,938811,940027,941675,943723,945583,946639,947003,947215,947511,947875,948363,949039,949783,950403,950959,951679,952635,953851,955499,957551,959447,960643,961327,962047,963003,964219,965871,967967,970075,971871,973703,976099,979227,983307,988651,994603,999343,1001679,1002299,1002511,1002807,1003171,1003659,1004335,1005079,1005699,1006255,1006975,1007931,1009147,1010795,1012847,1014743,1015939,1016623,1017343,1018299,1019515,1021167,1023263,1025371,1027167,1028999,1031395,1034523,1038603,1043947,1049903,1054679,1057155,1058095,1058815,1059771,1060987,1062639,1064735,1066843,1068639,1070471,1072867,1075995,1080075,1085423,1091423,1096411,1099487,1101575,1103971,1107099,1111183,1116583,1122883,1128895,1134319,1140379,1148299,1158635,1172139,1188779,1205419,1217195,1222315,1223343,1223359,1223387,1223423,1223463,1223523,1223611,1223695,1223751,1223811,1223903,1224015,1224155,1224363,1224619,1224815,1224903,1224963,1225055,1225167,1225307,1225515,1225775,1225999,1226171,1226383,1226679,1227043,1227531,1228203,1228907,1229359,1229511,1229571,1229663,1229775,1229915,1230123,1230383,1230607,1230779,1230991,1231287,1231651,1232139,1232811,1233519,1233999,1234235,1234447,1234743,1235107,1235595,1236271,1237015,1237635,1238191,1238911,1239867,1241083,1242731,1244779,1246635,1247663,1247943,1248003,1248095,1248207,1248347,1248555,1248815,1249039,1249211,1249423,1249719,1250083,1250571,1251243,1251951,1252431,1252667,1252879,1253175,1253539,1254027,1254703,1255447,1256067,1256623,1257343,1258299,1259515,1261163,1263211,1265071,1266127,1266491,1266703,1266999,1267363,1267851,1268527,1269271,1269891,1270447,1271167,1272123,1273339,1274987,1277039,1278935,1280131,1280815,1281535,1282491,1283707,1285359,1287455,1289563,1291359,1293191,1295587,1298715,1302795,1308139,1314091,1318827,1321135,1321671,1321731,1321823,1321935,1322075,1322283,1322543,1322767,1322939,1323151,1323447,1323811,1324299,1324971,1325679,1326159,1326395,1326607,1326903,1327267,1327755,1328431,1329175,1329795,1330351,1331071,1332027,1333243,1334891,1336939,1338799,1339855,1340219,1340431,1340727,1341091,1341579,1342255,1342999,1343619,1344175,1344895,1345851,1347067,1348715,1350767,1352663,1353859,1354543,1355263,1356219,1357435,1359087,1361183,1363291,1365087,1366919,1369315,1372443,1376523,1381867,1387819,1392559,1394895,1395515,1395727,1396023,1396387,1396875,1397551,1398295,1398915,1399471,1400191,1401147,1402363,1404011,1406063,1407959,1409155,1409839,1410559,1411515,1412731,1414383,1416479,1418587,1420383,1422215,1424611,1427739,1431819,1437163,1443119,1447895,1450371,1451311,1452031,1452987,1454203,1455855,1457951,1460059,1461855,1463687,1466083,1469211,1473291,1478639,1484639,1489627,1492703,1494791,1497187,1500315,1504399,1509799,1516099,1522111,1527535,1533595,1541515,1551851,1565355,1581995,1598635,1610411,1615535,1616583,1616643,1616735,1616847,1616987,1617195,1617455,1617679,1617851,1618063,1618359,1618723,1619211,1619883,1620591,1621071,1621307,1621519,1621815,1622179,1622667,1623343,1624087,1624707,1625263,1625983,1626939,1628155,1629803,1631851,1633711,1634767,1635131,1635343,1635639,1636003,1636491,1637167,1637911,1638531,1639087,1639807,1640763,1641979,1643627,1645679,1647575,1648771,1649455,1650175,1651131,1652347,1653999,1656095,1658203,1659999,1661831,1664227,1667355,1671435,1676779,1682731,1687471,1689807,1690427,1690639,1690935,1691299,1691787,1692463,1693207,1693827,1694383,1695103,1696059,1697275,1698923,1700975,1702871,1704067,1704751,1705471,1706427,1707643,1709295,1711391,1713499,1715295,1717127,1719523,1722651,1726731,1732075,1738031,1742807,1745283,1746223,1746943,1747899,1749115,1750767,1752863,1754971,1756767,1758599,1760995,1764123,1768203,1773551,1779551,1784539,1787615,1789703,1792099,1795227,1799311,1804711,1811011,1817023,1822447,1828507,1836427,1846763,1860267,1876907,1893547,1905327,1910479,1911611,1911823,1912119,1912483,1912971,1913647,1914391,1915011,1915567,1916287,1917243,1918459,1920107,1922159,1924055,1925251,1925935,1926655,1927611,1928827,1930479,1932575,1934683,1936479,1938311,1940707,1943835,1947915,1953259,1959215,1963991,1966467,1967407,1968127,1969083,1970299,1971951,1974047,1976155,1977951,1979783,1982179,1985307,1989387,1994735,2000735,2005723,2008799,2010887,2013283,2016411,2020495,2025895,2032195,2038207,2043631,2049691,2057611,2067947,2081451,2098091,2114735,2126551,2131843,2133295,2134015,2134971,2136187,2137839,2139935,2142043,2143839,2145671,2148067,2151195,2155275,2160623,2166623,2171611,2174687,2176775,2179171,2182299,2186383,2191783,2198083,2204095,2209519,2215579,2223499,2233835,2247339,2263983,2280671,2292699,2298591,2301191,2303587,2306715,2310799,2316199,2322499,2328511,2333935,2339995,2347915,2358251,2371759,2388455,2405443,2418495,2426735,2433307,2441227,2451567,2465135,2482235,2500847,2518295,2535203,2555243,2581419,2615595,2659243,2709163,2754219,2782891,2794155,2796203,2796207,2796215,2796227,2796239,2796255,2796283,2796315,2796335,2796351,2796379,2796415,2796455,2796515,2796603,2796683,2796719,2796735,2796763,2796799,2796839,2796899,2796987,2797071,2797127,2797187,2797279,2797391,2797531,2797739,2797995,2798187,2798255,2798271,2798299,2798335,2798375,2798435,2798523,2798607,2798663,2798723,2798815,2798927,2799067,2799275,2799531,2799727,2799815,2799875,2799967,2800079,2800219,2800427,2800687,2800911,2801083,2801295,2801591,2801955,2802443,2803115,2803819,2804267,2804399,2804415,2804443,2804479,2804519,2804579,2804667,2804751,2804807,2804867,2804959,2805071,2805211,2805419,2805675,2805871,2805959,2806019,2806111,2806223,2806363,2806571,2806831,2807055,2807227,2807439,2807735,2808099,2808587,2809259,2809963,2810415,2810567,2810627,2810719,2810831,2810971,2811179,2811439,2811663,2811835,2812047,2812343,2812707,2813195,2813867,2814575,2815055,2815291,2815503,2815799,2816163,2816651,2817327,2818071,2818691,2819247,2819967,2820923,2822139,2823787,2825835,2827691,2828715,2828975,2828991,2829019,2829055,2829095,2829155,2829243,2829327,2829383,2829443,2829535,2829647,2829787,2829995,2830251,2830447,2830535,2830595,2830687,2830799,2830939,2831147,2831407,2831631,2831803,2832015,2832311,2832675,2833163,2833835,2834539,2834991,2835143,2835203,2835295,2835407,2835547,2835755,2836015,2836239,2836411,2836623,2836919,2837283,2837771,2838443,2839151,2839631,2839867,2840079,2840375,2840739,2841227,2841903,2842647,2843267,2843823,2844543,2845499,2846715,2848363,2850411,2852267,2853295,2853575,2853635,2853727,2853839,2853979,2854187,2854447,2854671,2854843,2855055,2855351,2855715,2856203,2856875,2857583,2858063,2858299,2858511,2858807,2859171,2859659,2860335,2861079,2861699,2862255,2862975,2863931,2865147,2866795,2868843,2870703,2871759,2872123,2872335,2872631,2872995,2873483,2874159,2874903,2875523,2876079,2876799,2877755,2878971,2880619,2882671,2884567,2885763,2886447,2887167,2888123,2889339,2890991,2893087,2895195,2896991,2898823,2901219,2904347,2908427,2913771,2919723,2924459,2926763,2927279,2927295,2927323,2927359,2927399,2927459,2927547,2927631,2927687,2927747,2927839,2927951,2928091,2928299,2928555,2928751,2928839,2928899,2928991,2929103,2929243,2929451,2929711,2929935,2930107,2930319,2930615,2930979,2931467,2932139,2932843,2933295,2933447,2933507,2933599,2933711,2933851,2934059,2934319,2934543,2934715,2934927,2935223,2935587,2936075,2936747,2937455,2937935,2938171,2938383,2938679,2939043,2939531,2940207,2940951,2941571,2942127,2942847,2943803,2945019,2946667,2948715,2950571,2951599,2951879,2951939,2952031,2952143,2952283,2952491,2952751,2952975,2953147,2953359,2953655,2954019,2954507,2955179,2955887,2956367,2956603,2956815,2957111,2957475,2957963,2958639,2959383,2960003,2960559,2961279,2962235,2963451,2965099,2967147,2969007,2970063,2970427,2970639,2970935,2971299,2971787,2972463,2973207,2973827,2974383,2975103,2976059,2977275,2978923,2980975,2982871,2984067,2984751,2985471,2986427,2987643,2989295,2991391,2993499,2995295,2997127,2999523,3002651,3006731,3012075,3018027,3022763,3025071,3025607,3025667,3025759,3025871,3026011,3026219,3026479,3026703,3026875,3027087,3027383,3027747,3028235,3028907,3029615,3030095,3030331,3030543,3030839,3031203,3031691,3032367,3033111,3033731,3034287,3035007,3035963,3037179,3038827,3040875,3042735,3043791,3044155,3044367,3044663,3045027,3045515,3046191,3046935,3047555,3048111,3048831,3049787,3051003,3052651,3054703,3056599,3057795,3058479,3059199,3060155,3061371,3063023,3065119,3067227,3069023,3070855,3073251,3076379,3080459,3085803,3091755,3096495,3098831,3099451,3099663,3099959,3100323,3100811,3101487,3102231,3102851,3103407,3104127,3105083,3106299,3107947,3109999,3111895,3113091,3113775,3114495,3115451,3116667,3118319,3120415,3122523,3124319,3126151,3128547,3131675,3135755,3141099,3147055,3151831,3154307,3155247,3155967,3156923,3158139,3159791,3161887,3163995,3165791,3167623,3170019,3173147,3177227,3182575,3188575,3193563,3196639,3198727,3201123,3204251,3208335,3213735,3220035,3226047,3231471,3237531,3245451,3255787,3269291,3285931,3302571,3314347,3319467,3320495,3320511,3320539,3320575,3320615,3320675,3320763,3320847,3320903,3320963,3321055,3321167,3321307,3321515,3321771,3321967,3322055,3322115,3322207,3322319,3322459,3322667,3322927,3323151,3323323,3323535,3323831,3324195,3324683,3325355,3326059,3326511,3326663,3326723,3326815,3326927,3327067,3327275,3327535,3327759,3327931,3328143,3328439,3328803,3329291,3329963,3330671,3331151,3331387,3331599,3331895,3332259,3332747,3333423,3334167,3334787,3335343,3336063,3337019,3338235,3339883,3341931,3343787,3344815,3345095,3345155,3345247,3345359,3345499,3345707,3345967,3346191,3346363,3346575,3346871,3347235,3347723,3348395,3349103,3349583,3349819,3350031,3350327,3350691,3351179,3351855,3352599,3353219,3353775,3354495,3355451,3356667,3358315,3360363,3362223,3363279,3363643,3363855,3364151,3364515,3365003,3365679,3366423,3367043,3367599,3368319,3369275,3370491,3372139,3374191,3376087,3377283,3377967,3378687,3379643,3380859,3382511,3384607,3386715,3388511,3390343,3392739,3395867,3399947,3405291,3411243,3415979,3418287,3418823,3418883,3418975,3419087,3419227,3419435,3419695,3419919,3420091,3420303,3420599,3420963,3421451,3422123,3422831,3423311,3423547,3423759,3424055,3424419,3424907,3425583,3426327,3426947,3427503,3428223,3429179,3430395,3432043,3434091,3435951,3437007,3437371,3437583,3437879,3438243,3438731,3439407,3440151,3440771,3441327,3442047,3443003,3444219,3445867,3447919,3449815,3451011,3451695,3452415,3453371,3454587,3456239,3458335,3460443,3462239,3464071,3466467,3469595,3473675,3479019,3484971,3489711,3492047,3492667,3492879,3493175,3493539,3494027,3494703,3495447,3496067,3496623,3497343,3498299,3499515,3501163,3503215,3505111,3506307,3506991,3507711,3508667,3509883,3511535,3513631,3515739,3517535,3519367,3521763,3524891,3528971,3534315,3540271,3545047,3547523,3548463,3549183,3550139,3551355,3553007,3555103,3557211,3559007,3560839,3563235,3566363,3570443,3575791,3581791,3586779,3589855,3591943,3594339,3597467,3601551,3606951,3613251,3619263,3624687,3630747,3638667,3649003,3662507,3679147,3695787,3707563,3712687,3713735,3713795,3713887,3713999,3714139,3714347,3714607,3714831,3715003,3715215,3715511,3715875,3716363,3717035,3717743,3718223,3718459,3718671,3718967,3719331,3719819,3720495,3721239,3721859,3722415,3723135,3724091,3725307,3726955,3729003,3730863,3731919,3732283,3732495,3732791,3733155,3733643,3734319,3735063,3735683,3736239,3736959,3737915,3739131,3740779,3742831,3744727,3745923,3746607,3747327,3748283,3749499,3751151,3753247,3755355,3757151,3758983,3761379,3764507,3768587,3773931,3779883,3784623,3786959,3787579,3787791,3788087,3788451,3788939,3789615,3790359,3790979,3791535,3792255,3793211,3794427,3796075,3798127,3800023,3801219,3801903,3802623,3803579,3804795,3806447,3808543,3810651,3812447,3814279,3816675,3819803,3823883,3829227,3835183,3839959,3842435,3843375,3844095,3845051,3846267,3847919,3850015,3852123,3853919,3855751,3858147,3861275,3865355,3870703,3876703,3881691,3884767,3886855,3889251,3892379,3896463,3901863,3908163,3914175,3919599,3925659,3933579,3943915,3957419,3974059,3990699,4002479,4007631,4008763,4008975,4009271,4009635,4010123,4010799,4011543,4012163,4012719,4013439,4014395,4015611,4017259,4019311,4021207,4022403,4023087,4023807,4024763,4025979,4027631,4029727,4031835,4033631,4035463,4037859,4040987,4045067,4050411,4056367,4061143,4063619,4064559,4065279,4066235,4067451,4069103,4071199,4073307,4075103,4076935,4079331,4082459,4086539,4091887,4097887,4102875,4105951,4108039,4110435,4113563,4117647,4123047,4129347,4135359,4140783,4146843,4154763,4165099,4178603,4195243,4211887,4223703,4228995,4230447,4231167,4232123,4233339,4234991,4237087,4239195,4240991,4242823,4245219,4248347,4252427,4257775,4263775,4268763,4271839,4273927,4276323,4279451,4283535,4288935,4295235,4301247,4306671,4312731,4320651,4330987,4344491,4361135,4377823,4389851,4395743,4398343,4400739,4403867,4407951,4413351,4419651,4425663,4431087,4437147,4445067,4455403,4468911,4485607,4502595,4515647,4523887,4530459,4538379,4548719,4562287,4579387,4597999,4615447,4632355,4652395,4678571,4712747,4756395,4806315,4851371,4880043,4891307,4893359,4893375,4893403,4893439,4893479,4893539,4893627,4893711,4893767,4893827,4893919,4894031,4894171,4894379,4894635,4894831,4894919,4894979,4895071,4895183,4895323,4895531,4895791,4896015,4896187,4896399,4896695,4897059,4897547,4898219,4898923,4899375,4899527,4899587,4899679,4899791,4899931,4900139,4900399,4900623,4900795,4901007,4901303,4901667,4902155,4902827,4903535,4904015,4904251,4904463,4904759,4905123,4905611,4906287,4907031,4907651,4908207,4908927,4909883,4911099,4912747,4914795,4916651,4917679,4917959,4918019,4918111,4918223,4918363,4918571,4918831,4919055,4919227,4919439,4919735,4920099,4920587,4921259,4921967,4922447,4922683,4922895,4923191,4923555,4924043,4924719,4925463,4926083,4926639,4927359,4928315,4929531,4931179,4933227,4935087,4936143,4936507,4936719,4937015,4937379,4937867,4938543,4939287,4939907,4940463,4941183,4942139,4943355,4945003,4947055,4948951,4950147,4950831,4951551,4952507,4953723,4955375,4957471,4959579,4961375,4963207,4965603,4968731,4972811,4978155,4984107,4988843,4991151,4991687,4991747,4991839,4991951,4992091,4992299,4992559,4992783,4992955,4993167,4993463,4993827,4994315,4994987,4995695,4996175,4996411,4996623,4996919,4997283,4997771,4998447,4999191,4999811,5000367,5001087,5002043,5003259,5004907,5006955,5008815,5009871,5010235,5010447,5010743,5011107,5011595,5012271,5013015,5013635,5014191,5014911,5015867,5017083,5018731,5020783,5022679,5023875,5024559,5025279,5026235,5027451,5029103,5031199,5033307,5035103,5036935,5039331,5042459,5046539,5051883,5057835,5062575,5064911,5065531,5065743,5066039,5066403,5066891,5067567,5068311,5068931,5069487,5070207,5071163,5072379,5074027,5076079,5077975,5079171,5079855,5080575,5081531,5082747,5084399,5086495,5088603,5090399,5092231,5094627,5097755,5101835,5107179,5113135,5117911,5120387,5121327,5122047,5123003,5124219,5125871,5127967,5130075,5131871,5133703,5136099,5139227,5143307,5148655,5154655,5159643,5162719,5164807,5167203,5170331,5174415,5179815,5186115,5192127,5197551,5203611,5211531,5221867,5235371,5252011,5268651,5280427,5285551,5286599,5286659,5286751,5286863,5287003,5287211,5287471,5287695,5287867,5288079,5288375,5288739,5289227,5289899,5290607,5291087,5291323,5291535,5291831,5292195,5292683,5293359,5294103,5294723,5295279,5295999,5296955,5298171,5299819,5301867,5303727,5304783,5305147,5305359,5305655,5306019,5306507,5307183,5307927,5308547,5309103,5309823,5310779,5311995,5313643,5315695,5317591,5318787,5319471,5320191,5321147,5322363,5324015,5326111,5328219,5330015,5331847,5334243,5337371,5341451,5346795,5352747,5357487,5359823,5360443,5360655,5360951,5361315,5361803,5362479,5363223,5363843,5364399,5365119,5366075,5367291,5368939,5370991,5372887,5374083,5374767,5375487,5376443,5377659,5379311,5381407,5383515,5385311,5387143,5389539,5392667,5396747,5402091,5408047,5412823,5415299,5416239,5416959,5417915,5419131,5420783,5422879,5424987,5426783,5428615,5431011,5434139,5438219,5443567,5449567,5454555,5457631,5459719,5462115,5465243,5469327,5474727,5481027,5487039,5492463,5498523,5506443,5516779,5530283,5546923,5563563,5575343,5580495,5581627,5581839,5582135,5582499,5582987,5583663,5584407,5585027,5585583,5586303,5587259,5588475,5590123,5592175,5594071,5595267,5595951,5596671,5597627,5598843,5600495,5602591,5604699,5606495,5608327,5610723,5613851,5617931,5623275,5629231,5634007,5636483,5637423,5638143,5639099,5640315,5641967,5644063,5646171,5647967,5649799,5652195,5655323,5659403,5664751,5670751,5675739,5678815,5680903,5683299,5686427,5690511,5695911,5702211,5708223,5713647,5719707,5727627,5737963,5751467,5768107,5784751,5796567,5801859,5803311,5804031,5804987,5806203,5807855,5809951,5812059,5813855,5815687,5818083,5821211,5825291,5830639,5836639,5841627,5844703,5846791,5849187,5852315,5856399,5861799,5868099,5874111,5879535,5885595,5893515,5903851,5917355,5933999,5950687,5962715,5968607,5971207,5973603,5976731,5980815,5986215,5992515,5998527,6003951,6010011,6017931,6028267,6041775,6058471,6075459,6088511,6096751,6103323,6111243,6121583,6135151,6152251,6170863,6188311,6205219,6225259,6251435,6285611,6329259,6379179,6424235,6452907,6464175,6466247,6466307,6466399,6466511,6466651,6466859,6467119,6467343,6467515,6467727,6468023,6468387,6468875,6469547,6470255,6470735,6470971,6471183,6471479,6471843,6472331,6473007,6473751,6474371,6474927,6475647,6476603,6477819,6479467,6481515,6483375,6484431,6484795,6485007,6485303,6485667,6486155,6486831,6487575,6488195,6488751,6489471,6490427,6491643,6493291,6495343,6497239,6498435,6499119,6499839,6500795,6502011,6503663,6505759,6507867,6509663,6511495,6513891,6517019,6521099,6526443,6532395,6537135,6539471,6540091,6540303,6540599,6540963,6541451,6542127,6542871,6543491,6544047,6544767,6545723,6546939,6548587,6550639,6552535,6553731,6554415,6555135,6556091,6557307,6558959,6561055,6563163,6564959,6566791,6569187,6572315,6576395,6581739,6587695,6592471,6594947,6595887,6596607,6597563,6598779,6600431,6602527,6604635,6606431,6608263,6610659,6613787,6617867,6623215,6629215,6634203,6637279,6639367,6641763,6644891,6648975,6654375,6660675,6666687,6672111,6678171,6686091,6696427,6709931,6726571,6743211,6754991,6760143,6761275,6761487,6761783,6762147,6762635,6763311,6764055,6764675,6765231,6765951,6766907,6768123,6769771,6771823,6773719,6774915,6775599,6776319,6777275,6778491,6780143,6782239,6784347,6786143,6787975,6790371,6793499,6797579,6802923,6808879,6813655,6816131,6817071,6817791,6818747,6819963,6821615,6823711,6825819,6827615,6829447,6831843,6834971,6839051,6844399,6850399,6855387,6858463,6860551,6862947,6866075,6870159,6875559,6881859,6887871,6893295,6899355,6907275,6917611,6931115,6947755,6964399,6976215,6981507,6982959,6983679,6984635,6985851,6987503,6989599,6991707,6993503,6995335,6997731,7000859,7004939,7010287,7016287,7021275,7024351,7026439,7028835,7031963,7036047,7041447,7047747,7053759,7059183,7065243,7073163,7083499,7097003,7113647,7130335,7142363,7148255,7150855,7153251,7156379,7160463,7165863,7172163,7178175,7183599,7189659,7197579,7207915,7221423,7238119,7255107,7268159,7276399,7282971,7290891,7301231,7314799,7331899,7350511,7367959,7384867,7404907,7431083,7465259,7508907,7558827,7603883,7632559,7643855,7646011,7646223,7646519,7646883,7647371,7648047,7648791,7649411,7649967,7650687,7651643,7652859,7654507,7656559,7658455,7659651,7660335,7661055,7662011,7663227,7664879,7666975,7669083,7670879,7672711,7675107,7678235,7682315,7687659,7693615,7698391,7700867,7701807,7702527,7703483,7704699,7706351,7708447,7710555,7712351,7714183,7716579,7719707,7723787,7729135,7735135,7740123,7743199,7745287,7747683,7750811,7754895,7760295,7766595,7772607,7778031,7784091,7792011,7802347,7815851,7832491,7849135,7860951,7866243,7867695,7868415,7869371,7870587,7872239,7874335,7876443,7878239,7880071,7882467,7885595,7889675,7895023,7901023,7906011,7909087,7911175,7913571,7916699,7920783,7926183,7932483,7938495,7943919,7949979,7957899,7968235,7981739,7998383,8015071,8027099,8032991,8035591,8037987,8041115,8045199,8050599,8056899,8062911,8068335,8074395,8082315,8092651,8106159,8122855,8139843,8152895,8161135,8167707,8175627,8185967,8199535,8216635,8235247,8252695,8269603,8289643,8315819,8349995,8393643,8443563,8488623,8517335,8528771,8531247,8531967,8532923,8534139,8535791,8537887,8539995,8541791,8543623,8546019,8549147,8553227,8558575,8564575,8569563,8572639,8574727,8577123,8580251,8584335,8589735,8596035,8602047,8607471,8613531,8621451,8631787,8645291,8661935,8678623,8690651,8696543,8699143,8701539,8704667,8708751,8714151,8720451,8726463,8731887,8737947,8745867,8756203,8769711,8786407,8803395,8816447,8824687,8831259,8839179,8849519,8863087,8880187,8898799,8916247,8933155,8953195,8979371,9013547,9057195,9107119,9152223,9181147,9193183,9196807,9199203,9202331,9206415,9211815,9218115,9224127,9229551,9235611,9243531,9253867,9267375,9284071,9301059,9314111,9322351,9328923,9336843,9347183,9360751,9377851,9396463,9413911,9430819,9450859,9477035,9511211,9554863,9604839,9650243,9680191,9694575,9702171,9710091,9720431,9733999,9751099,9769711,9787159,9804067,9824107,9850283,9884463,9928175,9978555,10025583,10059927,10082979,10104043,10130223,10164471,10208707,10261519,10316191,10367995,10421851,10488107,10574635,10686635,10823851,10968747,11087531,11156139,11180715,11184811,11184815,11184823,11184835,11184847,11184863,11184891,11184923,11184943,11184959,11184987,11185023,11185063,11185123,11185211,11185291,11185327,11185343,11185371,11185407,11185447,11185507,11185595,11185679,11185735,11185795,11185887,11185999,11186139,11186347,11186603,11186795,11186863,11186879,11186907,11186943,11186983,11187043,11187131,11187215,11187271,11187331,11187423,11187535,11187675,11187883,11188139,11188335,11188423,11188483,11188575,11188687,11188827,11189035,11189295,11189519,11189691,11189903,11190199,11190563,11191051,11191723,11192427,11192875,11193007,11193023,11193051,11193087,11193127,11193187,11193275,11193359,11193415,11193475,11193567,11193679,11193819,11194027,11194283,11194479,11194567,11194627,11194719,11194831,11194971,11195179,11195439,11195663,11195835,11196047,11196343,11196707,11197195,11197867,11198571,11199023,11199175,11199235,11199327,11199439,11199579,11199787,11200047,11200271,11200443,11200655,11200951,11201315,11201803,11202475,11203183,11203663,11203899,11204111,11204407,11204771,11205259,11205935,11206679,11207299,11207855,11208575,11209531,11210747,11212395,11214443,11216299,11217323,11217583,11217599,11217627,11217663,11217703,11217763,11217851,11217935,11217991,11218051,11218143,11218255,11218395,11218603,11218859,11219055,11219143,11219203,11219295,11219407,11219547,11219755,11220015,11220239,11220411,11220623,11220919,11221283,11221771,11222443,11223147,11223599,11223751,11223811,11223903,11224015,11224155,11224363,11224623,11224847,11225019,11225231,11225527,11225891,11226379,11227051,11227759,11228239,11228475,11228687,11228983,11229347,11229835,11230511,11231255,11231875,11232431,11233151,11234107,11235323,11236971,11239019,11240875,11241903,11242183,11242243,11242335,11242447,11242587,11242795,11243055,11243279,11243451,11243663,11243959,11244323,11244811,11245483,11246191,11246671,11246907,11247119,11247415,11247779,11248267,11248943,11249687,11250307,11250863,11251583,11252539,11253755,11255403,11257451,11259311,11260367,11260731,11260943,11261239,11261603,11262091,11262767,11263511,11264131,11264687,11265407,11266363,11267579,11269227,11271279,11273175,11274371,11275055,11275775,11276731,11277947,11279599,11281695,11283803,11285599,11287431,11289827,11292955,11297035,11302379,11308331,11313067,11315371,11315887,11315903,11315931,11315967,11316007,11316067,11316155,11316239,11316295,11316355,11316447,11316559,11316699,11316907,11317163,11317359,11317447,11317507,11317599,11317711,11317851,11318059,11318319,11318543,11318715,11318927,11319223,11319587,11320075,11320747,11321451,11321903,11322055,11322115,11322207,11322319,11322459,11322667,11322927,11323151,11323323,11323535,11323831,11324195,11324683,11325355,11326063,11326543,11326779,11326991,11327287,11327651,11328139,11328815,11329559,11330179,11330735,11331455,11332411,11333627,11335275,11337323,11339179,11340207,11340487,11340547,11340639,11340751,11340891,11341099,11341359,11341583,11341755,11341967,11342263,11342627,11343115,11343787,11344495,11344975,11345211,11345423,11345719,11346083,11346571,11347247,11347991,11348611,11349167,11349887,11350843,11352059,11353707,11355755,11357615,11358671,11359035,11359247,11359543,11359907,11360395,11361071,11361815,11362435,11362991,11363711,11364667,11365883,11367531,11369583,11371479,11372675,11373359,11374079,11375035,11376251,11377903,11379999,11382107,11383903,11385735,11388131,11391259,11395339,11400683,11406635,11411371,11413679,11414215,11414275,11414367,11414479,11414619,11414827,11415087,11415311,11415483,11415695,11415991,11416355,11416843,11417515,11418223,11418703,11418939,11419151,11419447,11419811,11420299,11420975,11421719,11422339,11422895,11423615,11424571,11425787,11427435,11429483,11431343,11432399,11432763,11432975,11433271,11433635,11434123,11434799,11435543,11436163,11436719,11437439,11438395,11439611,11441259,11443311,11445207,11446403,11447087,11447807,11448763,11449979,11451631,11453727,11455835,11457631,11459463,11461859,11464987,11469067,11474411,11480363,11485103,11487439,11488059,11488271,11488567,11488931,11489419,11490095,11490839,11491459,11492015,11492735,11493691,11494907,11496555,11498607,11500503,11501699,11502383,11503103,11504059,11505275,11506927,11509023,11511131,11512927,11514759,11517155,11520283,11524363,11529707,11535663,11540439,11542915,11543855,11544575,11545531,11546747,11548399,11550495,11552603,11554399,11556231,11558627,11561755,11565835,11571183,11577183,11582171,11585247,11587335,11589731,11592859,11596943,11602343,11608643,11614655,11620079,11626139,11634059,11644395,11657899,11674539,11691179,11702955,11708075,11709103,11709119,11709147,11709183,11709223,11709283,11709371,11709455,11709511,11709571,11709663,11709775,11709915,11710123,11710379,11710575,11710663,11710723,11710815,11710927,11711067,11711275,11711535,11711759,11711931,11712143,11712439,11712803,11713291,11713963,11714667,11715119,11715271,11715331,11715423,11715535,11715675,11715883,11716143,11716367,11716539,11716751,11717047,11717411,11717899,11718571,11719279,11719759,11719995,11720207,11720503,11720867,11721355,11722031,11722775,11723395,11723951,11724671,11725627,11726843,11728491,11730539,11732395,11733423,11733703,11733763,11733855,11733967,11734107,11734315,11734575,11734799,11734971,11735183,11735479,11735843,11736331,11737003,11737711,11738191,11738427,11738639,11738935,11739299,11739787,11740463,11741207,11741827,11742383,11743103,11744059,11745275,11746923,11748971,11750831,11751887,11752251,11752463,11752759,11753123,11753611,11754287,11755031,11755651,11756207,11756927,11757883,11759099,11760747,11762799,11764695,11765891,11766575,11767295,11768251,11769467,11771119,11773215,11775323,11777119,11778951,11781347,11784475,11788555,11793899,11799851,11804587,11806895,11807431,11807491,11807583,11807695,11807835,11808043,11808303,11808527,11808699,11808911,11809207,11809571,11810059,11810731,11811439,11811919,11812155,11812367,11812663,11813027,11813515,11814191,11814935,11815555,11816111,11816831,11817787,11819003,11820651,11822699,11824559,11825615,11825979,11826191,11826487,11826851,11827339,11828015,11828759,11829379,11829935,11830655,11831611,11832827,11834475,11836527,11838423,11839619,11840303,11841023,11841979,11843195,11844847,11846943,11849051,11850847,11852679,11855075,11858203,11862283,11867627,11873579,11878319,11880655,11881275,11881487,11881783,11882147,11882635,11883311,11884055,11884675,11885231,11885951,11886907,11888123,11889771,11891823,11893719,11894915,11895599,11896319,11897275,11898491,11900143,11902239,11904347,11906143,11907975,11910371,11913499,11917579,11922923,11928879,11933655,11936131,11937071,11937791,11938747,11939963,11941615,11943711,11945819,11947615,11949447,11951843,11954971,11959051,11964399,11970399,11975387,11978463,11980551,11982947,11986075,11990159,11995559,12001859,12007871,12013295,12019355,12027275,12037611,12051115,12067755,12084395,12096171,12101295,12102343,12102403,12102495,12102607,12102747,12102955,12103215,12103439,12103611,12103823,12104119,12104483,12104971,12105643,12106351,12106831,12107067,12107279,12107575,12107939,12108427,12109103,12109847,12110467,12111023,12111743,12112699,12113915,12115563,12117611,12119471,12120527,12120891,12121103,12121399,12121763,12122251,12122927,12123671,12124291,12124847,12125567,12126523,12127739,12129387,12131439,12133335,12134531,12135215,12135935,12136891,12138107,12139759,12141855,12143963,12145759,12147591,12149987,12153115,12157195,12162539,12168491,12173231,12175567,12176187,12176399,12176695,12177059,12177547,12178223,12178967,12179587,12180143,12180863,12181819,12183035,12184683,12186735,12188631,12189827,12190511,12191231,12192187,12193403,12195055,12197151,12199259,12201055,12202887,12205283,12208411,12212491,12217835,12223791,12228567,12231043,12231983,12232703,12233659,12234875,12236527,12238623,12240731,12242527,12244359,12246755,12249883,12253963,12259311,12265311,12270299,12273375,12275463,12277859,12280987,12285071,12290471,12296771,12302783,12308207,12314267,12322187,12332523,12346027,12362667,12379307,12391087,12396239,12397371,12397583,12397879,12398243,12398731,12399407,12400151,12400771,12401327,12402047,12403003,12404219,12405867,12407919,12409815,12411011,12411695,12412415,12413371,12414587,12416239,12418335,12420443,12422239,12424071,12426467,12429595,12433675,12439019,12444975,12449751,12452227,12453167,12453887,12454843,12456059,12457711,12459807,12461915,12463711,12465543,12467939,12471067,12475147,12480495,12486495,12491483,12494559,12496647,12499043,12502171,12506255,12511655,12517955,12523967,12529391,12535451,12543371,12553707,12567211,12583851,12600495,12612311,12617603,12619055,12619775,12620731,12621947,12623599,12625695,12627803,12629599,12631431,12633827,12636955,12641035,12646383,12652383,12657371,12660447,12662535,12664931,12668059,12672143,12677543,12683843,12689855,12695279,12701339,12709259,12719595,12733099,12749743,12766431,12778459,12784351,12786951,12789347,12792475,12796559,12801959,12808259,12814271,12819695,12825755,12833675,12844011,12857519,12874215,12891203,12904255,12912495,12919067,12926987,12937327,12950895,12967995,12986607,13004055,13020963,13041003,13067179,13101355,13145003,13194923,13239979,13268651,13279915,13281967,13281983,13282011,13282047,13282087,13282147,13282235,13282319,13282375,13282435,13282527,13282639,13282779,13282987,13283243,13283439,13283527,13283587,13283679,13283791,13283931,13284139,13284399,13284623,13284795,13285007,13285303,13285667,13286155,13286827,13287531,13287983,13288135,13288195,13288287,13288399,13288539,13288747,13289007,13289231,13289403,13289615,13289911,13290275,13290763,13291435,13292143,13292623,13292859,13293071,13293367,13293731,13294219,13294895,13295639,13296259,13296815,13297535,13298491,13299707,13301355,13303403,13305259,13306287,13306567,13306627,13306719,13306831,13306971,13307179,13307439,13307663,13307835,13308047,13308343,13308707,13309195,13309867,13310575,13311055,13311291,13311503,13311799,13312163,13312651,13313327,13314071,13314691,13315247,13315967,13316923,13318139,13319787,13321835,13323695,13324751,13325115,13325327,13325623,13325987,13326475,13327151,13327895,13328515,13329071,13329791,13330747,13331963,13333611,13335663,13337559,13338755,13339439,13340159,13341115,13342331,13343983,13346079,13348187,13349983,13351815,13354211,13357339,13361419,13366763,13372715,13377451,13379759,13380295,13380355,13380447,13380559,13380699,13380907,13381167,13381391,13381563,13381775,13382071,13382435,13382923,13383595,13384303,13384783,13385019,13385231,13385527,13385891,13386379,13387055,13387799,13388419,13388975,13389695,13390651,13391867,13393515,13395563,13397423,13398479,13398843,13399055,13399351,13399715,13400203,13400879,13401623,13402243,13402799,13403519,13404475,13405691,13407339,13409391,13411287,13412483,13413167,13413887,13414843,13416059,13417711,13419807,13421915,13423711,13425543,13427939,13431067,13435147,13440491,13446443,13451183,13453519,13454139,13454351,13454647,13455011,13455499,13456175,13456919,13457539,13458095,13458815,13459771,13460987,13462635,13464687,13466583,13467779,13468463,13469183,13470139,13471355,13473007,13475103,13477211,13479007,13480839,13483235,13486363,13490443,13495787,13501743,13506519,13508995,13509935,13510655,13511611,13512827,13514479,13516575,13518683,13520479,13522311,13524707,13527835,13531915,13537263,13543263,13548251,13551327,13553415,13555811,13558939,13563023,13568423,13574723,13580735,13586159,13592219,13600139,13610475,13623979,13640619,13657259,13669035,13674159,13675207,13675267,13675359,13675471,13675611,13675819,13676079,13676303,13676475,13676687,13676983,13677347,13677835,13678507,13679215,13679695,13679931,13680143,13680439,13680803,13681291,13681967,13682711,13683331,13683887,13684607,13685563,13686779,13688427,13690475,13692335,13693391,13693755,13693967,13694263,13694627,13695115,13695791,13696535,13697155,13697711,13698431,13699387,13700603,13702251,13704303,13706199,13707395,13708079,13708799,13709755,13710971,13712623,13714719,13716827,13718623,13720455,13722851,13725979,13730059,13735403,13741355,13746095,13748431,13749051,13749263,13749559,13749923,13750411,13751087,13751831,13752451,13753007,13753727,13754683,13755899,13757547,13759599,13761495,13762691,13763375,13764095,13765051,13766267,13767919,13770015,13772123,13773919,13775751,13778147,13781275,13785355,13790699,13796655,13801431,13803907,13804847,13805567,13806523,13807739,13809391,13811487,13813595,13815391,13817223,13819619,13822747,13826827,13832175,13838175,13843163,13846239,13848327,13850723,13853851,13857935,13863335,13869635,13875647,13881071,13887131,13895051,13905387,13918891,13935531,13952171,13963951,13969103,13970235,13970447,13970743,13971107,13971595,13972271,13973015,13973635,13974191,13974911,13975867,13977083,13978731,13980783,13982679,13983875,13984559,13985279,13986235,13987451,13989103,13991199,13993307,13995103,13996935,13999331,14002459,14006539,14011883,14017839,14022615,14025091,14026031,14026751,14027707,14028923,14030575,14032671,14034779,14036575,14038407,14040803,14043931,14048011,14053359,14059359,14064347,14067423,14069511,14071907,14075035,14079119,14084519,14090819,14096831,14102255,14108315,14116235,14126571,14140075,14156715,14173359,14185175,14190467,14191919,14192639,14193595,14194811,14196463,14198559,14200667,14202463,14204295,14206691,14209819,14213899,14219247,14225247,14230235,14233311,14235399,14237795,14240923,14245007,14250407,14256707,14262719,14268143,14274203,14282123,14292459,14305963,14322607,14339295,14351323,14357215,14359815,14362211,14365339,14369423,14374823,14381123,14387135,14392559,14398619,14406539,14416875,14430383,14447079,14464067,14477119,14485359,14491931,14499851,14510191,14523759,14540859,14559471,14576919,14593827,14613867,14640043,14674219,14717867,14767787,14812843,14841515,14852783,14854855,14854915,14855007,14855119,14855259,14855467,14855727,14855951,14856123,14856335,14856631,14856995,14857483,14858155,14858863,14859343,14859579,14859791,14860087,14860451,14860939,14861615,14862359,14862979,14863535,14864255,14865211,14866427,14868075,14870123,14871983,14873039,14873403,14873615,14873911,14874275,14874763,14875439,14876183,14876803,14877359,14878079,14879035,14880251,14881899,14883951,14885847,14887043,14887727,14888447,14889403,14890619,14892271,14894367,14896475,14898271,14900103,14902499,14905627,14909707,14915051,14921003,14925743,14928079,14928699,14928911,14929207,14929571,14930059,14930735,14931479,14932099,14932655,14933375,14934331,14935547,14937195,14939247,14941143,14942339,14943023,14943743,14944699,14945915,14947567,14949663,14951771,14953567,14955399,14957795,14960923,14965003,14970347,14976303,14981079,14983555,14984495,14985215,14986171,14987387,14989039,14991135,14993243,14995039,14996871,14999267,15002395,15006475,15011823,15017823,15022811,15025887,15027975,15030371,15033499,15037583,15042983,15049283,15055295,15060719,15066779,15074699,15085035,15098539,15115179,15131819,15143599,15148751,15149883,15150095,15150391,15150755,15151243,15151919,15152663,15153283,15153839,15154559,15155515,15156731,15158379,15160431,15162327,15163523,15164207,15164927,15165883,15167099,15168751,15170847,15172955,15174751,15176583,15178979,15182107,15186187,15191531,15197487,15202263,15204739,15205679,15206399,15207355,15208571,15210223,15212319,15214427,15216223,15218055,15220451,15223579,15227659,15233007,15239007,15243995,15247071,15249159,15251555,15254683,15258767,15264167,15270467,15276479,15281903,15287963,15295883,15306219,15319723,15336363,15353007,15364823,15370115,15371567,15372287,15373243,15374459,15376111,15378207,15380315,15382111,15383943,15386339,15389467,15393547,15398895,15404895,15409883,15412959,15415047,15417443,15420571,15424655,15430055,15436355,15442367,15447791,15453851,15461771,15472107,15485611,15502255,15518943,15530971,15536863,15539463,15541859,15544987,15549071,15554471,15560771,15566783,15572207,15578267,15586187,15596523,15610031,15626727,15643715,15656767,15665007,15671579,15679499,15689839,15703407,15720507,15739119,15756567,15773475,15793515,15819691,15853867,15897515,15947435,15992491,16021167,16032463,16034619,16034831,16035127,16035491,16035979,16036655,16037399,16038019,16038575,16039295,16040251,16041467,16043115,16045167,16047063,16048259,16048943,16049663,16050619,16051835,16053487,16055583,16057691,16059487,16061319,16063715,16066843,16070923,16076267,16082223,16086999,16089475,16090415,16091135,16092091,16093307,16094959,16097055,16099163,16100959,16102791,16105187,16108315,16112395,16117743,16123743,16128731,16131807,16133895,16136291,16139419,16143503,16148903,16155203,16161215,16166639,16172699,16180619,16190955,16204459,16221099,16237743,16249559,16254851,16256303,16257023,16257979,16259195,16260847,16262943,16265051,16266847,16268679,16271075,16274203,16278283,16283631,16289631,16294619,16297695,16299783,16302179,16305307,16309391,16314791,16321091,16327103,16332527,16338587,16346507,16356843,16370347,16386991,16403679,16415707,16421599,16424199,16426595,16429723,16433807,16439207,16445507,16451519,16456943,16463003,16470923,16481259,16494767,16511463,16528451,16541503,16549743,16556315,16564235,16574575,16588143,16605243,16623855,16641303,16658211,16678251,16704427,16738603,16782251,16832171,16877231,16905943,16917379,16919855,16920575,16921531,16922747,16924399,16926495,16928603,16930399,16932231,16934627,16937755,16941835,16947183,16953183,16958171,16961247,16963335,16965731,16968859,16972943,16978343,16984643,16990655,16996079,17002139,17010059,17020395,17033899,17050543,17067231,17079259,17085151,17087751,17090147,17093275,17097359,17102759,17109059,17115071,17120495,17126555,17134475,17144811,17158319,17175015,17192003,17205055,17213295,17219867,17227787,17238127,17251695,17268795,17287407,17304855,17321763,17341803,17367979,17402155,17445803,17495727,17540831,17569755,17581791,17585415,17587811,17590939,17595023,17600423,17606723,17612735,17618159,17624219,17632139,17642475,17655983,17672679,17689667,17702719,17710959,17717531,17725451,17735791,17749359,17766459,17785071,17802519,17819427,17839467,17865643,17899819,17943471,17993447,18038851,18068799,18083183,18090779,18098699,18109039,18122607,18139707,18158319,18175767,18192675,18212715,18238891,18273071,18316783,18367163,18414191,18448535,18471587,18492651,18518831,18553079,18597315,18650127,18704799,18756603,18810459,18876715,18963243,19075243,19212459,19357355,19476139,19544747,19569323,19573423,19573439,19573467,19573503,19573543,19573603,19573691,19573775,19573831,19573891,19573983,19574095,19574235,19574443,19574699,19574895,19574983,19575043,19575135,19575247,19575387,19575595,19575855,19576079,19576251,19576463,19576759,19577123,19577611,19578283,19578987,19579439,19579591,19579651,19579743,19579855,19579995,19580203,19580463,19580687,19580859,19581071,19581367,19581731,19582219,19582891,19583599,19584079,19584315,19584527,19584823,19585187,19585675,19586351,19587095,19587715,19588271,19588991,19589947,19591163,19592811,19594859,19596715,19597743,19598023,19598083,19598175,19598287,19598427,19598635,19598895,19599119,19599291,19599503,19599799,19600163,19600651,19601323,19602031,19602511,19602747,19602959,19603255,19603619,19604107,19604783,19605527,19606147,19606703,19607423,19608379,19609595,19611243,19613291,19615151,19616207,19616571,19616783,19617079,19617443,19617931,19618607,19619351,19619971,19620527,19621247,19622203,19623419,19625067,19627119,19629015,19630211,19630895,19631615,19632571,19633787,19635439,19637535,19639643,19641439,19643271,19645667,19648795,19652875,19658219,19664171,19668907,19671215,19671751,19671811,19671903,19672015,19672155,19672363,19672623,19672847,19673019,19673231,19673527,19673891,19674379,19675051,19675759,19676239,19676475,19676687,19676983,19677347,19677835,19678511,19679255,19679875,19680431,19681151,19682107,19683323,19684971,19687019,19688879,19689935,19690299,19690511,19690807,19691171,19691659,19692335,19693079,19693699,19694255,19694975,19695931,19697147,19698795,19700847,19702743,19703939,19704623,19705343,19706299,19707515,19709167,19711263,19713371,19715167,19716999,19719395,19722523,19726603,19731947,19737899,19742639,19744975,19745595,19745807,19746103,19746467,19746955,19747631,19748375,19748995,19749551,19750271,19751227,19752443,19754091,19756143,19758039,19759235,19759919,19760639,19761595,19762811,19764463,19766559,19768667,19770463,19772295,19774691,19777819,19781899,19787243,19793199,19797975,19800451,19801391,19802111,19803067,19804283,19805935,19808031,19810139,19811935,19813767,19816163,19819291,19823371,19828719,19834719,19839707,19842783,19844871,19847267,19850395,19854479,19859879,19866179,19872191,19877615,19883675,19891595,19901931,19915435,19932075,19948715,19960491,19965615,19966663,19966723,19966815,19966927,19967067,19967275,19967535,19967759,19967931,19968143,19968439,19968803,19969291,19969963,19970671,19971151,19971387,19971599,19971895,19972259,19972747,19973423,19974167,19974787,19975343,19976063,19977019,19978235,19979883,19981931,19983791,19984847,19985211,19985423,19985719,19986083,19986571,19987247,19987991,19988611,19989167,19989887,19990843,19992059,19993707,19995759,19997655,19998851,19999535,20000255,20001211,20002427,20004079,20006175,20008283,20010079,20011911,20014307,20017435,20021515,20026859,20032811,20037551,20039887,20040507,20040719,20041015,20041379,20041867,20042543,20043287,20043907,20044463,20045183,20046139,20047355,20049003,20051055,20052951,20054147,20054831,20055551,20056507,20057723,20059375,20061471,20063579,20065375,20067207,20069603,20072731,20076811,20082155,20088111,20092887,20095363,20096303,20097023,20097979,20099195,20100847,20102943,20105051,20106847,20108679,20111075,20114203,20118283,20123631,20129631,20134619,20137695,20139783,20142179,20145307,20149391,20154791,20161091,20167103,20172527,20178587,20186507,20196843,20210347,20226987,20243627,20255407,20260559,20261691,20261903,20262199,20262563,20263051,20263727,20264471,20265091,20265647,20266367,20267323,20268539,20270187,20272239,20274135,20275331,20276015,20276735,20277691,20278907,20280559,20282655,20284763,20286559,20288391,20290787,20293915,20297995,20303339,20309295,20314071,20316547,20317487,20318207,20319163,20320379,20322031,20324127,20326235,20328031,20329863,20332259,20335387,20339467,20344815,20350815,20355803,20358879,20360967,20363363,20366491,20370575,20375975,20382275,20388287,20393711,20399771,20407691,20418027,20431531,20448171,20464815,20476631,20481923,20483375,20484095,20485051,20486267,20487919,20490015,20492123,20493919,20495751,20498147,20501275,20505355,20510703,20516703,20521691,20524767,20526855,20529251,20532379,20536463,20541863,20548163,20554175,20559599,20565659,20573579,20583915,20597419,20614063,20630751,20642779,20648671,20651271,20653667,20656795,20660879,20666279,20672579,20678591,20684015,20690075,20697995,20708331,20721839,20738535,20755523,20768575,20776815,20783387,20791307,20801647,20815215,20832315,20850927,20868375,20885283,20905323,20931499,20965675,21009323,21059243,21104299,21132971,21144239,21146311,21146371,21146463,21146575,21146715,21146923,21147183,21147407,21147579,21147791,21148087,21148451,21148939,21149611,21150319,21150799,21151035,21151247,21151543,21151907,21152395,21153071,21153815,21154435,21154991,21155711,21156667,21157883,21159531,21161579,21163439,21164495,21164859,21165071,21165367,21165731,21166219,21166895,21167639,21168259,21168815,21169535,21170491,21171707,21173355,21175407,21177303,21178499,21179183,21179903,21180859,21182075,21183727,21185823,21187931,21189727,21191559,21193955,21197083,21201163,21206507,21212459,21217199,21219535,21220155,21220367,21220663,21221027,21221515,21222191,21222935,21223555,21224111,21224831,21225787,21227003,21228651,21230703,21232599,21233795,21234479,21235199,21236155,21237371,21239023,21241119,21243227,21245023,21246855,21249251,21252379,21256459,21261803,21267759,21272535,21275011,21275951,21276671,21277627,21278843,21280495,21282591,21284699,21286495,21288327,21290723,21293851,21297931,21303279,21309279,21314267,21317343,21319431,21321827,21324955,21329039,21334439,21340739,21346751,21352175,21358235,21366155,21376491,21389995,21406635,21423275,21435055,21440207,21441339,21441551,21441847,21442211,21442699,21443375,21444119,21444739,21445295,21446015,21446971,21448187,21449835,21451887,21453783,21454979,21455663,21456383,21457339,21458555,21460207,21462303,21464411,21466207,21468039,21470435,21473563,21477643,21482987,21488943,21493719,21496195,21497135,21497855,21498811,21500027,21501679,21503775,21505883,21507679,21509511,21511907,21515035,21519115,21524463,21530463,21535451,21538527,21540615,21543011,21546139,21550223,21555623,21561923,21567935,21573359,21579419,21587339,21597675,21611179,21627819,21644463,21656279,21661571,21663023,21663743,21664699,21665915,21667567,21669663,21671771,21673567,21675399,21677795,21680923,21685003,21690351,21696351,21701339,21704415,21706503,21708899,21712027,21716111,21721511,21727811,21733823,21739247,21745307,21753227,21763563,21777067,21793711,21810399,21822427,21828319,21830919,21833315,21836443,21840527,21845927,21852227,21858239,21863663,21869723,21877643,21887979,21901487,21918183,21935171,21948223,21956463,21963035,21970955,21981295,21994863,22011963,22030575,22048023,22064931,22084971,22111147,22145323,22188971,22238891,22283947,22312623,22323919,22326075,22326287,22326583,22326947,22327435,22328111,22328855,22329475,22330031,22330751,22331707,22332923,22334571,22336623,22338519,22339715,22340399,22341119,22342075,22343291,22344943,22347039,22349147,22350943,22352775,22355171,22358299,22362379,22367723,22373679,22378455,22380931,22381871,22382591,22383547,22384763,22386415,22388511,22390619,22392415,22394247,22396643,22399771,22403851,22409199,22415199,22420187,22423263,22425351,22427747,22430875,22434959,22440359,22446659,22452671,22458095,22464155,22472075,22482411,22495915,22512555,22529199,22541015,22546307,22547759,22548479,22549435,22550651,22552303,22554399,22556507,22558303,22560135,22562531,22565659,22569739,22575087,22581087,22586075,22589151,22591239,22593635,22596763,22600847,22606247,22612547,22618559,22623983,22630043,22637963,22648299,22661803,22678447,22695135,22707163,22713055,22715655,22718051,22721179,22725263,22730663,22736963,22742975,22748399,22754459,22762379,22772715,22786223,22802919,22819907,22832959,22841199,22847771,22855691,22866031,22879599,22896699,22915311,22932759,22949667,22969707,22995883,23030059,23073707,23123627,23168687,23197399,23208835,23211311,23212031,23212987,23214203,23215855,23217951,23220059,23221855,23223687,23226083,23229211,23233291,23238639,23244639,23249627,23252703,23254791,23257187,23260315,23264399,23269799,23276099,23282111,23287535,23293595,23301515,23311851,23325355,23341999,23358687,23370715,23376607,23379207,23381603,23384731,23388815,23394215,23400515,23406527,23411951,23418011,23425931,23436267,23449775,23466471,23483459,23496511,23504751,23511323,23519243,23529583,23543151,23560251,23578863,23596311,23613219,23633259,23659435,23693611,23737259,23787183,23832287,23861211,23873247,23876871,23879267,23882395,23886479,23891879,23898179,23904191,23909615,23915675,23923595,23933931,23947439,23964135,23981123,23994175,24002415,24008987,24016907,24027247,24040815,24057915,24076527,24093975,24110883,24130923,24157099,24191275,24234927,24284903,24330307,24360255,24374639,24382235,24390155,24400495,24414063,24431163,24449775,24467223,24484131,24504171,24530347,24564527,24608239,24658619,24705647,24739991,24763043,24784107,24810287,24844535,24888771,24941583,24996255,25048059,25101915,25168171,25254699,25366699,25503915,25648811,25767595,25836203,25860783,25864903,25864963,25865055,25865167,25865307,25865515,25865775,25865999,25866171,25866383,25866679,25867043,25867531,25868203,25868911,25869391,25869627,25869839,25870135,25870499,25870987,25871663,25872407,25873027,25873583,25874303,25875259,25876475,25878123,25880171,25882031,25883087,25883451,25883663,25883959,25884323,25884811,25885487,25886231,25886851,25887407,25888127,25889083,25890299,25891947,25893999,25895895,25897091,25897775,25898495,25899451,25900667,25902319,25904415,25906523,25908319,25910151,25912547,25915675,25919755,25925099,25931051,25935791,25938127,25938747,25938959,25939255,25939619,25940107,25940783,25941527,25942147,25942703,25943423,25944379,25945595,25947243,25949295,25951191,25952387,25953071,25953791,25954747,25955963,25957615,25959711,25961819,25963615,25965447,25967843,25970971,25975051,25980395,25986351,25991127,25993603,25994543,25995263,25996219,25997435,25999087,26001183,26003291,26005087,26006919,26009315,26012443,26016523,26021871,26027871,26032859,26035935,26038023,26040419,26043547,26047631,26053031,26059331,26065343,26070767,26076827,26084747,26095083,26108587,26125227,26141867,26153647,26158799,26159931,26160143,26160439,26160803,26161291,26161967,26162711,26163331,26163887,26164607,26165563,26166779,26168427,26170479,26172375,26173571,26174255,26174975,26175931,26177147,26178799,26180895,26183003,26184799,26186631,26189027,26192155,26196235,26201579,26207535,26212311,26214787,26215727,26216447,26217403,26218619,26220271,26222367,26224475,26226271,26228103,26230499,26233627,26237707,26243055,26249055,26254043,26257119,26259207,26261603,26264731,26268815,26274215,26280515,26286527,26291951,26298011,26305931,26316267,26329771,26346411,26363055,26374871,26380163,26381615,26382335,26383291,26384507,26386159,26388255,26390363,26392159,26393991,26396387,26399515,26403595,26408943,26414943,26419931,26423007,26425095,26427491,26430619,26434703,26440103,26446403,26452415,26457839,26463899,26471819,26482155,26495659,26512303,26528991,26541019,26546911,26549511,26551907,26555035,26559119,26564519,26570819,26576831,26582255,26588315,26596235,26606571,26620079,26636775,26653763,26666815,26675055,26681627,26689547,26699887,26713455,26730555,26749167,26766615,26783523,26803563,26829739,26863915,26907563,26957483,27002539,27031215,27042511,27044667,27044879,27045175,27045539,27046027,27046703,27047447,27048067,27048623,27049343,27050299,27051515,27053163,27055215,27057111,27058307,27058991,27059711,27060667,27061883,27063535,27065631,27067739,27069535,27071367,27073763,27076891,27080971,27086315,27092271,27097047,27099523,27100463,27101183,27102139,27103355,27105007,27107103,27109211,27111007,27112839,27115235,27118363,27122443,27127791,27133791,27138779,27141855,27143943,27146339,27149467,27153551,27158951,27165251,27171263,27176687,27182747,27190667,27201003,27214507,27231147,27247791,27259607,27264899,27266351,27267071,27268027,27269243,27270895,27272991,27275099,27276895,27278727,27281123,27284251,27288331,27293679,27299679,27304667,27307743,27309831,27312227,27315355,27319439,27324839,27331139,27337151,27342575,27348635,27356555,27366891,27380395,27397039,27413727,27425755,27431647,27434247,27436643,27439771,27443855,27449255,27455555,27461567,27466991,27473051,27480971,27491307,27504815,27521511,27538499,27551551,27559791,27566363,27574283,27584623,27598191,27615291,27633903,27651351,27668259,27688299,27714475,27748651,27792299,27842219,27887279,27915991,27927427,27929903,27930623,27931579,27932795,27934447,27936543,27938651,27940447,27942279,27944675,27947803,27951883,27957231,27963231,27968219,27971295,27973383,27975779,27978907,27982991,27988391,27994691,28000703,28006127,28012187,28020107,28030443,28043947,28060591,28077279,28089307,28095199,28097799,28100195,28103323,28107407,28112807,28119107,28125119,28130543,28136603,28144523,28154859,28168367,28185063,28202051,28215103,28223343,28229915,28237835,28248175,28261743,28278843,28297455,28314903,28331811,28351851,28378027,28412203,28455851,28505775,28550879,28579803,28591839,28595463,28597859,28600987,28605071,28610471,28616771,28622783,28628207,28634267,28642187,28652523,28666031,28682727,28699715,28712767,28721007,28727579,28735499,28745839,28759407,28776507,28795119,28812567,28829475,28849515,28875691,28909867,28953519,29003495,29048899,29078847,29093231,29100827,29108747,29119087,29132655,29149755,29168367,29185815,29202723,29222763,29248939,29283119,29326831,29377211,29424239,29458583,29481635,29502699,29528879,29563127,29607363,29660175,29714847,29766651,29820507,29886763,29973291,30085291,30222507,30367403,30486187,30554799,30579407,30583611,30583823,30584119,30584483,30584971,30585647,30586391,30587011,30587567,30588287,30589243,30590459,30592107,30594159,30596055,30597251,30597935,30598655,30599611,30600827,30602479,30604575,30606683,30608479,30610311,30612707,30615835,30619915,30625259,30631215,30635991,30638467,30639407,30640127,30641083,30642299,30643951,30646047,30648155,30649951,30651783,30654179,30657307,30661387,30666735,30672735,30677723,30680799,30682887,30685283,30688411,30692495,30697895,30704195,30710207,30715631,30721691,30729611,30739947,30753451,30770091,30786735,30798551,30803843,30805295,30806015,30806971,30808187,30809839,30811935,30814043,30815839,30817671,30820067,30823195,30827275,30832623,30838623,30843611,30846687,30848775,30851171,30854299,30858383,30863783,30870083,30876095,30881519,30887579,30895499,30905835,30919339,30935983,30952671,30964699,30970591,30973191,30975587,30978715,30982799,30988199,30994499,31000511,31005935,31011995,31019915,31030251,31043759,31060455,31077443,31090495,31098735,31105307,31113227,31123567,31137135,31154235,31172847,31190295,31207203,31227243,31253419,31287595,31331243,31381163,31426223,31454935,31466371,31468847,31469567,31470523,31471739,31473391,31475487,31477595,31479391,31481223,31483619,31486747,31490827,31496175,31502175,31507163,31510239,31512327,31514723,31517851,31521935,31527335,31533635,31539647,31545071,31551131,31559051,31569387,31582891,31599535,31616223,31628251,31634143,31636743,31639139,31642267,31646351,31651751,31658051,31664063,31669487,31675547,31683467,31693803,31707311,31724007,31740995,31754047,31762287,31768859,31776779,31787119,31800687,31817787,31836399,31853847,31870755,31890795,31916971,31951147,31994795,32044719,32089823,32118747,32130783,32134407,32136803,32139931,32144015,32149415,32155715,32161727,32167151,32173211,32181131,32191467,32204975,32221671,32238659,32251711,32259951,32266523,32274443,32284783,32298351,32315451,32334063,32351511,32368419,32388459,32414635,32448811,32492463,32542439,32587843,32617791,32632175,32639771,32647691,32658031,32671599,32688699,32707311,32724759,32741667,32761707,32787883,32822063,32865775,32916155,32963183,32997527,33020579,33041643,33067823,33102071,33146307,33199119,33253791,33305595,33359451,33425707,33512235,33624235,33761451,33906347,34025135,34093783,34118531,34123055,34123775,34124731,34125947,34127599,34129695,34131803,34133599,34135431,34137827,34140955,34145035,34150383,34156383,34161371,34164447,34166535,34168931,34172059,34176143,34181543,34187843,34193855,34199279,34205339,34213259,34223595,34237099,34253743,34270431,34282459,34288351,34290951,34293347,34296475,34300559,34305959,34312259,34318271,34323695,34329755,34337675,34348011,34361519,34378215,34395203,34408255,34416495,34423067,34430987,34441327,34454895,34471995,34490607,34508055,34524963,34545003,34571179,34605355,34649003,34698927,34744031,34772955,34784991,34788615,34791011,34794139,34798223,34803623,34809923,34815935,34821359,34827419,34835339,34845675,34859183,34875879,34892867,34905919,34914159,34920731,34928651,34938991,34952559,34969659,34988271,35005719,35022627,35042667,35068843,35103019,35146671,35196647,35242051,35271999,35286383,35293979,35301899,35312239,35325807,35342907,35361519,35378967,35395875,35415915,35442091,35476271,35519983,35570363,35617391,35651735,35674787,35695851,35722031,35756279,35800515,35853327,35907999,35959803,36013659,36079915,36166443,36278443,36415659,36560559,36679391,36748251,36773599,36779271,36781667,36784795,36788879,36794279,36800579,36806591,36812015,36818075,36825995,36836331,36849839,36866535,36883523,36896575,36904815,36911387,36919307,36929647,36943215,36960315,36978927,36996375,37013283,37033323,37059499,37093675,37137327,37187303,37232707,37262655,37277039,37284635,37292555,37302895,37316463,37333563,37352175,37369623,37386531,37406571,37432747,37466927,37510639,37561019,37608047,37642391,37665443,37686507,37712687,37746935,37791171,37843983,37898655,37950459,38004315,38070571,38157099,38269099,38406319,38551271,38670403,38740287,38767983,38777627,38785547,38795887,38809455,38826555,38845167,38862615,38879523,38899563,38925739,38959919,39003631,39054011,39101039,39135383,39158435,39179499,39205679,39239927,39284163,39336975,39391647,39443451,39497307,39563563,39650091,39762095,39899375,40044731,40165487,40239767,40276131,40299243,40325423,40359671,40403907,40456719,40511391,40563195,40617051,40683307,40769839,40881911,41019715,41167503,41295903,41387643,41454811,41523119,41609727,41722459,41863743,42024039,42185187,42342651,42516619,42735659,43020715,43381931,43801259,44209835,44516011,44677803,44731051,44739243,44739247,44739255,44739267,44739279,44739295,44739323,44739355,44739375,44739391,44739419,44739455,44739495,44739555,44739643,44739723,44739759,44739775,44739803,44739839,44739879,44739939,44740027,44740111,44740167,44740227,44740319,44740431,44740571,44740779,44741035,44741227,44741295,44741311,44741339,44741375,44741415,44741475,44741563,44741647,44741703,44741763,44741855,44741967,44742107,44742315,44742571,44742767,44742855,44742915,44743007,44743119,44743259,44743467,44743727,44743951,44744123,44744335,44744631,44744995,44745483,44746155,44746859,44747307,44747439,44747455,44747483,44747519,44747559,44747619,44747707,44747791,44747847,44747907,44747999,44748111,44748251,44748459,44748715,44748911,44748999,44749059,44749151,44749263,44749403,44749611,44749871,44750095,44750267,44750479,44750775,44751139,44751627,44752299,44753003,44753455,44753607,44753667,44753759,44753871,44754011,44754219,44754479,44754703,44754875,44755087,44755383,44755747,44756235,44756907,44757615,44758095,44758331,44758543,44758839,44759203,44759691,44760367,44761111,44761731,44762287,44763007,44763963,44765179,44766827,44768875,44770731,44771755,44772015,44772031,44772059,44772095,44772135,44772195,44772283,44772367,44772423,44772483,44772575,44772687,44772827,44773035,44773291,44773487,44773575,44773635,44773727,44773839,44773979,44774187,44774447,44774671,44774843,44775055,44775351,44775715,44776203,44776875,44777579,44778031,44778183,44778243,44778335,44778447,44778587,44778795,44779055,44779279,44779451,44779663,44779959,44780323,44780811,44781483,44782191,44782671,44782907,44783119,44783415,44783779,44784267,44784943,44785687,44786307,44786863,44787583,44788539,44789755,44791403,44793451,44795307,44796335,44796615,44796675,44796767,44796879,44797019,44797227,44797487,44797711,44797883,44798095,44798391,44798755,44799243,44799915,44800623,44801103,44801339,44801551,44801847,44802211,44802699,44803375,44804119,44804739,44805295,44806015,44806971,44808187,44809835,44811883,44813743,44814799,44815163,44815375,44815671,44816035,44816523,44817199,44817943,44818563,44819119,44819839,44820795,44822011,44823659,44825711,44827607,44828803,44829487,44830207,44831163,44832379,44834031,44836127,44838235,44840031,44841863,44844259,44847387,44851467,44856811,44862763,44867499,44869803,44870319,44870335,44870363,44870399,44870439,44870499,44870587,44870671,44870727,44870787,44870879,44870991,44871131,44871339,44871595,44871791,44871879,44871939,44872031,44872143,44872283,44872491,44872751,44872975,44873147,44873359,44873655,44874019,44874507,44875179,44875883,44876335,44876487,44876547,44876639,44876751,44876891,44877099,44877359,44877583,44877755,44877967,44878263,44878627,44879115,44879787,44880495,44880975,44881211,44881423,44881719,44882083,44882571,44883247,44883991,44884611,44885167,44885887,44886843,44888059,44889707,44891755,44893611,44894639,44894919,44894979,44895071,44895183,44895323,44895531,44895791,44896015,44896187,44896399,44896695,44897059,44897547,44898219,44898927,44899407,44899643,44899855,44900151,44900515,44901003,44901679,44902423,44903043,44903599,44904319,44905275,44906491,44908139,44910187,44912047,44913103,44913467,44913679,44913975,44914339,44914827,44915503,44916247,44916867,44917423,44918143,44919099,44920315,44921963,44924015,44925911,44927107,44927791,44928511,44929467,44930683,44932335,44934431,44936539,44938335,44940167,44942563,44945691,44949771,44955115,44961067,44965803,44968111,44968647,44968707,44968799,44968911,44969051,44969259,44969519,44969743,44969915,44970127,44970423,44970787,44971275,44971947,44972655,44973135,44973371,44973583,44973879,44974243,44974731,44975407,44976151,44976771,44977327,44978047,44979003,44980219,44981867,44983915,44985775,44986831,44987195,44987407,44987703,44988067,44988555,44989231,44989975,44990595,44991151,44991871,44992827,44994043,44995691,44997743,44999639,45000835,45001519,45002239,45003195,45004411,45006063,45008159,45010267,45012063,45013895,45016291,45019419,45023499,45028843,45034795,45039535,45041871,45042491,45042703,45042999,45043363,45043851,45044527,45045271,45045891,45046447,45047167,45048123,45049339,45050987,45053039,45054935,45056131,45056815,45057535,45058491,45059707,45061359,45063455,45065563,45067359,45069191,45071587,45074715,45078795,45084139,45090095,45094871,45097347,45098287,45099007,45099963,45101179,45102831,45104927,45107035,45108831,45110663,45113059,45116187,45120267,45125615,45131615,45136603,45139679,45141767,45144163,45147291,45151375,45156775,45163075,45169087,45174511,45180571,45188491,45198827,45212331,45228971,45245611,45257387,45262507,45263535,45263551,45263579,45263615,45263655,45263715,45263803,45263887,45263943,45264003,45264095,45264207,45264347,45264555,45264811,45265007,45265095,45265155,45265247,45265359,45265499,45265707,45265967,45266191,45266363,45266575,45266871,45267235,45267723,45268395,45269099,45269551,45269703,45269763,45269855,45269967,45270107,45270315,45270575,45270799,45270971,45271183,45271479,45271843,45272331,45273003,45273711,45274191,45274427,45274639,45274935,45275299,45275787,45276463,45277207,45277827,45278383,45279103,45280059,45281275,45282923,45284971,45286827,45287855,45288135,45288195,45288287,45288399,45288539,45288747,45289007,45289231,45289403,45289615,45289911,45290275,45290763,45291435,45292143,45292623,45292859,45293071,45293367,45293731,45294219,45294895,45295639,45296259,45296815,45297535,45298491,45299707,45301355,45303403,45305263,45306319,45306683,45306895,45307191,45307555,45308043,45308719,45309463,45310083,45310639,45311359,45312315,45313531,45315179,45317231,45319127,45320323,45321007,45321727,45322683,45323899,45325551,45327647,45329755,45331551,45333383,45335779,45338907,45342987,45348331,45354283,45359019,45361327,45361863,45361923,45362015,45362127,45362267,45362475,45362735,45362959,45363131,45363343,45363639,45364003,45364491,45365163,45365871,45366351,45366587,45366799,45367095,45367459,45367947,45368623,45369367,45369987,45370543,45371263,45372219,45373435,45375083,45377131,45378991,45380047,45380411,45380623,45380919,45381283,45381771,45382447,45383191,45383811,45384367,45385087,45386043,45387259,45388907,45390959,45392855,45394051,45394735,45395455,45396411,45397627,45399279,45401375,45403483,45405279,45407111,45409507,45412635,45416715,45422059,45428011,45432751,45435087,45435707,45435919,45436215,45436579,45437067,45437743,45438487,45439107,45439663,45440383,45441339,45442555,45444203,45446255,45448151,45449347,45450031,45450751,45451707,45452923,45454575,45456671,45458779,45460575,45462407,45464803,45467931,45472011,45477355,45483311,45488087,45490563,45491503,45492223,45493179,45494395,45496047,45498143,45500251,45502047,45503879,45506275,45509403,45513483,45518831,45524831,45529819,45532895,45534983,45537379,45540507,45544591,45549991,45556291,45562303,45567727,45573787,45581707,45592043,45605547,45622187,45638827,45650603,45655727,45656775,45656835,45656927,45657039,45657179,45657387,45657647,45657871,45658043,45658255,45658551,45658915,45659403,45660075,45660783,45661263,45661499,45661711,45662007,45662371,45662859,45663535,45664279,45664899,45665455,45666175,45667131,45668347,45669995,45672043,45673903,45674959,45675323,45675535,45675831,45676195,45676683,45677359,45678103,45678723,45679279,45679999,45680955,45682171,45683819,45685871,45687767,45688963,45689647,45690367,45691323,45692539,45694191,45696287,45698395,45700191,45702023,45704419,45707547,45711627,45716971,45722923,45727663,45729999,45730619,45730831,45731127,45731491,45731979,45732655,45733399,45734019,45734575,45735295,45736251,45737467,45739115,45741167,45743063,45744259,45744943,45745663,45746619,45747835,45749487,45751583,45753691,45755487,45757319,45759715,45762843,45766923,45772267,45778223,45782999,45785475,45786415,45787135,45788091,45789307,45790959,45793055,45795163,45796959,45798791,45801187,45804315,45808395,45813743,45819743,45824731,45827807,45829895,45832291,45835419,45839503,45844903,45851203,45857215,45862639,45868699,45876619,45886955,45900459,45917099,45933739,45945519,45950671,45951803,45952015,45952311,45952675,45953163,45953839,45954583,45955203,45955759,45956479,45957435,45958651,45960299,45962351,45964247,45965443,45966127,45966847,45967803,45969019,45970671,45972767,45974875,45976671,45978503,45980899,45984027,45988107,45993451,45999407,46004183,46006659,46007599,46008319,46009275,46010491,46012143,46014239,46016347,46018143,46019975,46022371,46025499,46029579,46034927,46040927,46045915,46048991,46051079,46053475,46056603,46060687,46066087,46072387,46078399,46083823,46089883,46097803,46108139,46121643,46138283,46154927,46166743,46172035,46173487,46174207,46175163,46176379,46178031,46180127,46182235,46184031,46185863,46188259,46191387,46195467,46200815,46206815,46211803,46214879,46216967,46219363,46222491,46226575,46231975,46238275,46244287,46249711,46255771,46263691,46274027,46287531,46304175,46320863,46332891,46338783,46341383,46343779,46346907,46350991,46356391,46362691,46368703,46374127,46380187,46388107,46398443,46411951,46428647,46445635,46458687,46466927,46473499,46481419,46491759,46505327,46522427,46541039,46558487,46575395,46595435,46621611,46655787,46699435,46749355,46794411,46823083,46834347,46836399,46836415,46836443,46836479,46836519,46836579,46836667,46836751,46836807,46836867,46836959,46837071,46837211,46837419,46837675,46837871,46837959,46838019,46838111,46838223,46838363,46838571,46838831,46839055,46839227,46839439,46839735,46840099,46840587,46841259,46841963,46842415,46842567,46842627,46842719,46842831,46842971,46843179,46843439,46843663,46843835,46844047,46844343,46844707,46845195,46845867,46846575,46847055,46847291,46847503,46847799,46848163,46848651,46849327,46850071,46850691,46851247,46851967,46852923,46854139,46855787,46857835,46859691,46860719,46860999,46861059,46861151,46861263,46861403,46861611,46861871,46862095,46862267,46862479,46862775,46863139,46863627,46864299,46865007,46865487,46865723,46865935,46866231,46866595,46867083,46867759,46868503,46869123,46869679,46870399,46871355,46872571,46874219,46876267,46878127,46879183,46879547,46879759,46880055,46880419,46880907,46881583,46882327,46882947,46883503,46884223,46885179,46886395,46888043,46890095,46891991,46893187,46893871,46894591,46895547,46896763,46898415,46900511,46902619,46904415,46906247,46908643,46911771,46915851,46921195,46927147,46931883,46934191,46934727,46934787,46934879,46934991,46935131,46935339,46935599,46935823,46935995,46936207,46936503,46936867,46937355,46938027,46938735,46939215,46939451,46939663,46939959,46940323,46940811,46941487,46942231,46942851,46943407,46944127,46945083,46946299,46947947,46949995,46951855,46952911,46953275,46953487,46953783,46954147,46954635,46955311,46956055,46956675,46957231,46957951,46958907,46960123,46961771,46963823,46965719,46966915,46967599,46968319,46969275,46970491,46972143,46974239,46976347,46978143,46979975,46982371,46985499,46989579,46994923,47000875,47005615,47007951,47008571,47008783,47009079,47009443,47009931,47010607,47011351,47011971,47012527,47013247,47014203,47015419,47017067,47019119,47021015,47022211,47022895,47023615,47024571,47025787,47027439,47029535,47031643,47033439,47035271,47037667,47040795,47044875,47050219,47056175,47060951,47063427,47064367,47065087,47066043,47067259,47068911,47071007,47073115,47074911,47076743,47079139,47082267,47086347,47091695,47097695,47102683,47105759,47107847,47110243,47113371,47117455,47122855,47129155,47135167,47140591,47146651,47154571,47164907,47178411,47195051,47211691,47223467,47228591,47229639,47229699,47229791,47229903,47230043,47230251,47230511,47230735,47230907,47231119,47231415,47231779,47232267,47232939,47233647,47234127,47234363,47234575,47234871,47235235,47235723,47236399,47237143,47237763,47238319,47239039,47239995,47241211,47242859,47244907,47246767,47247823,47248187,47248399,47248695,47249059,47249547,47250223,47250967,47251587,47252143,47252863,47253819,47255035,47256683,47258735,47260631,47261827,47262511,47263231,47264187,47265403,47267055,47269151,47271259,47273055,47274887,47277283,47280411,47284491,47289835,47295787,47300527,47302863,47303483,47303695,47303991,47304355,47304843,47305519,47306263,47306883,47307439,47308159,47309115,47310331,47311979,47314031,47315927,47317123,47317807,47318527,47319483,47320699,47322351,47324447,47326555,47328351,47330183,47332579,47335707,47339787,47345131,47351087,47355863,47358339,47359279,47359999,47360955,47362171,47363823,47365919,47368027,47369823,47371655,47374051,47377179,47381259,47386607,47392607,47397595,47400671,47402759,47405155,47408283,47412367,47417767,47424067,47430079,47435503,47441563,47449483,47459819,47473323,47489963,47506603,47518383,47523535,47524667,47524879,47525175,47525539,47526027,47526703,47527447,47528067,47528623,47529343,47530299,47531515,47533163,47535215,47537111,47538307,47538991,47539711,47540667,47541883,47543535,47545631,47547739,47549535,47551367,47553763,47556891,47560971,47566315,47572271,47577047,47579523,47580463,47581183,47582139,47583355,47585007,47587103,47589211,47591007,47592839,47595235,47598363,47602443,47607791,47613791,47618779,47621855,47623943,47626339,47629467,47633551,47638951,47645251,47651263,47656687,47662747,47670667,47681003,47694507,47711147,47727791,47739607,47744899,47746351,47747071,47748027,47749243,47750895,47752991,47755099,47756895,47758727,47761123,47764251,47768331,47773679,47779679,47784667,47787743,47789831,47792227,47795355,47799439,47804839,47811139,47817151,47822575,47828635,47836555,47846891,47860395,47877039,47893727,47905755,47911647,47914247,47916643,47919771,47923855,47929255,47935555,47941567,47946991,47953051,47960971,47971307,47984815,48001511,48018499,48031551,48039791,48046363,48054283,48064623,48078191,48095291,48113903,48131351,48148259,48168299,48194475,48228651,48272299,48322219,48367275,48395947,48407215,48409287,48409347,48409439,48409551,48409691,48409899,48410159,48410383,48410555,48410767,48411063,48411427,48411915,48412587,48413295,48413775,48414011,48414223,48414519,48414883,48415371,48416047,48416791,48417411,48417967,48418687,48419643,48420859,48422507,48424555,48426415,48427471,48427835,48428047,48428343,48428707,48429195,48429871,48430615,48431235,48431791,48432511,48433467,48434683,48436331,48438383,48440279,48441475,48442159,48442879,48443835,48445051,48446703,48448799,48450907,48452703,48454535,48456931,48460059,48464139,48469483,48475435,48480175,48482511,48483131,48483343,48483639,48484003,48484491,48485167,48485911,48486531,48487087,48487807,48488763,48489979,48491627,48493679,48495575,48496771,48497455,48498175,48499131,48500347,48501999,48504095,48506203,48507999,48509831,48512227,48515355,48519435,48524779,48530735,48535511,48537987,48538927,48539647,48540603,48541819,48543471,48545567,48547675,48549471,48551303,48553699,48556827,48560907,48566255,48572255,48577243,48580319,48582407,48584803,48587931,48592015,48597415,48603715,48609727,48615151,48621211,48629131,48639467,48652971,48669611,48686251,48698031,48703183,48704315,48704527,48704823,48705187,48705675,48706351,48707095,48707715,48708271,48708991,48709947,48711163,48712811,48714863,48716759,48717955,48718639,48719359,48720315,48721531,48723183,48725279,48727387,48729183,48731015,48733411,48736539,48740619,48745963,48751919,48756695,48759171,48760111,48760831,48761787,48763003,48764655,48766751,48768859,48770655,48772487,48774883,48778011,48782091,48787439,48793439,48798427,48801503,48803591,48805987,48809115,48813199,48818599,48824899,48830911,48836335,48842395,48850315,48860651,48874155,48890795,48907439,48919255,48924547,48925999,48926719,48927675,48928891,48930543,48932639,48934747,48936543,48938375,48940771,48943899,48947979,48953327,48959327,48964315,48967391,48969479,48971875,48975003,48979087,48984487,48990787,48996799,49002223,49008283,49016203,49026539,49040043,49056687,49073375,49085403,49091295,49093895,49096291,49099419,49103503,49108903,49115203,49121215,49126639,49132699,49140619,49150955,49164463,49181159,49198147,49211199,49219439,49226011,49233931,49244271,49257839,49274939,49293551,49310999,49327907,49347947,49374123,49408299,49451947,49501867,49546923,49575599,49586895,49589051,49589263,49589559,49589923,49590411,49591087,49591831,49592451,49593007,49593727,49594683,49595899,49597547,49599599,49601495,49602691,49603375]

def toothpick(n):
    return v[n]

from math import floor, log

"""
See: https://oeis.org/A139250
Formulas:
  Let n = msb(n) + j where msb(n) = A053644(n)
  let a(0) = 0. 
  Then a(n) = (2 * msb(n)^2 + 1) / 3 + 2 * a(j) + a(j + 1) - 1
    - David A. Corneth, Mar 26 2015
    
Note: A053644(n) is the sequence of largest power of 2 <= n
See: https://oeis.org/A053644
"""

def toothpick(n):
    """Returns number of picks required for n rounds of the toothpick sequence"""
    if n < 2:
        return n
    
    msb_n = 2 ** floor(log(n, 2))
    j = n - msb_n
    return (2 * msb_n ** 2 + 1) / 3 + 2 * toothpick(j) + toothpick(j + 1) - 1

import math

def isPowerOfTwo (n):
    return (math.ceil(math.log2(n)) == math.floor(math.log2(n)))

def toothpick(n):
    """Returns number of picks required for n rounds of the toothpick sequence"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif isPowerOfTwo (n):
        return int((2**(2*math.log2(n)+1)+1) / 3)
    k = int (math.log2(n))
    i = n - 2**k
    
    return toothpick (2**k) + 2*toothpick(i) + toothpick (i+1) - 1

from math import log
from functools import lru_cache

@lru_cache(5000)
def toothpick(n):
    if n == 0:
        return 0
    else:
        k = int(log(n, 2))
        i = n - 2**k
        if i == 0:
            return (2**(2*k+1)+1)/3
        else:
            return toothpick(2**k) + 2 * toothpick(i) + toothpick(i+1) - 1

# from collections import deque
# from time import monotonic
# from numpy import zeros
# from itertools import chain

# _r = zeros((5000, 5000))
# _n = 0
# _q1 = [(2500, 2500)]
# _q2 = []
# _c = 0
# _t = monotonic()

# def toothpick(n):
#     print(n)
#     nonlocal _n, _q1, _q2, _c, _t
#     t = _t
#     if n > 2100:
#         raise Exception(n)
#     r = _r
#     q1 = _q1
#     q2 = _q2
#     count = _c
#     t1 = 0
#     t2 = 0
#     for round in range(_n, n):
#         dx = 1 if round % 2 == 1 else 0
#         dy = 0 if round % 2 == 1 else 1
#         tmp = monotonic()
#         re = []
#         ap = re.append
#         r_m = 0
        
#         for xy in chain(q1, q2):

#             r_m = r[xy]
#             if r_m == 0:
#                 r[xy] = round
#                 ap(xy)
# #                 count += 1
#             else:
#                 if r_m == round:
#                     r[xy] = -1
# #                     count -= 1
#         t1 += monotonic() - tmp
#         tmp = monotonic()
#         q1 = [(xy[0]+dx, xy[1]+dy) for xy in re if r[xy] == round]
#         q2 = [(xy[0]-dx, xy[1]-dy) for xy in re if r[xy] == round]
#         count += len(q1)
#         t2 += monotonic() - tmp
    
    
#     print(n, count, monotonic() - t, t1, t2)
#     _n = n
#     _q1 = q1
#     _q2 = q2
#     _c = count
#     return count


# from https://oeis.org/A139250

def msb(n):
    t = 0
    while (n >> t) > 0:
        t += 1

    return 2 ** (t - 1)

def toothpick(n):
    k = (2 * msb(n) ** 2 + 1) // 3

    if n == 0:
        return 0
    elif n == msb(n):
        return k
    else:
        return k + 2*toothpick(n - msb(n)) + toothpick(n - msb(n) + 1) - 1

from math import log2
def toothpick(n):
    if n == 0:
        return 0
    k = int(log2(n))
    i = n - 2**k
    if i == 0:
        return (2**(2*k+1)+1)//3
    else:
        return toothpick(2**k) + 2*toothpick(i)+ toothpick(i+1) - 1