#include <bits/stdc++.h>
using namespace std;
vector<int> solve{-1,0,0,2,2,2,4,7,7,14,14,19,21,24,27,35,35,40,47,55,55,72,77,86,88,94,97,118,121,130,138,150,150,176,181,196,203,215,223,246,246,260,277,294,299,330,339,357,359,383,389,421,424,442,463,486,489,530,539,562,570,591,603,661,661,679,705,731,736,783,798,825,832,858,870,914,922,966,989,1019,1019,1081,1095,1127,1144,1170,1187,1240,1245,1277,1308,1350,1359,1421,1439,1477,1479,1514,1538,1624,1630,1666,1698,1737,1740,1823,1841,1882,1903,1942,1965,2033,2036,2077,2118,2163,2172,2254,2277,2333,2341,2396,2417,2494,2506,2548,2606,2654,2654,2740,2758,2808,2834,2905,2931,3030,3035,3085,3132,3185,3200,3292,3319,3381,3388,3436,3462,3584,3596,3650,3694,3751,3759,3869,3913,3973,3996,4053,4083,4181,4181,4265,4327,4389,4403,4525,4557,4620,4637,4697,4723,4860,4877,4940,4993,5074,5079,5195,5227,5295,5326,5392,5434,5547,5556,5619,5681,5764,5782,5962,6000,6072,6074,6145,6180,6296,6320,6392,6478,6553,6559,6690,6726,6822,6854,6925,6964,7124,7127,7231,7314,7394,7412,7549,7590,7673,7694,7805,7844,7981,8004,8081,8149,8233,8236,8393,8434,8520,8561,8645,8690,8911,8920,9006,9088,9178,9201,9353,9409,9499,9507,9596,9651,9835,9856,9976,10053,10154,10166,10327,10369,10464,10522,10644,10692,10847,10847,10942,11028,11151,11169,11353,11403,11502,11528,11621,11692,11859,11885,11984,12083,12185,12190,12408,12458,12577,12624,12726,12779,12990,13005,13109,13201,13308,13335,13532,13594,13731,13738,13844,13892,14074,14100,14208,14330,14443,14455,14718,14772,14892,14936,15088,15145,15333,15341,15449,15559,15675,15719,15916,15976,16093,16116,16232,16289,16575,16605,16722,16820,16960,16960,17166,17250,17384,17446,17557,17619,17822,17836,18001,18123,18248,18280,18515,18578,18706,18723,18848,18908,19120,19146,19307,19444,19615,19632,19865,19928,20059,20112,20241,20322,20580,20585,20716,20832,20967,20999,21286,21354,21489,21520,21671,21737,22012,22054,22185,22298,22436,22445,22708,22771,22948,23010,23148,23231,23461,23479,23614,23794,23937,23975,24217,24289,24433,24435,24653,24724,25014,25049,25193,25309,25467,25491,25742,25814,25964,26050,26197,26272,26628,26634,26783,26914,27073,27109,27411,27507,27686,27718,27870,27941,28198,28237,28443,28603,28761,28764,29030,29134,29292,29375,29531,29611,29924,29942,30091,30228,30432,30473,30790,30873,31035,31056,31217,31328,31594,31633,31830,31967,32132,32155,32570,32647,32814,32882,33043,33127,33405,33408,33575,33732,33932,33973,34260,34346,34559,34600,34770,34854,35195,35240,35411,35632,35806,35815,36123,36209,36385,36467,36700,36790,37083,37106,37327,37479,37673,37729,38066,38156,38336,38344,38518,38607,39029,39084,39260,39444,39627,39648,39959,40079,40264,40341,40520,40621,41037,41049,41295,41456,41644,41686,42003,42098,42287,42345,42528,42650,42964,43012,43201,43356,43601,43601,44023,44118,44313,44399,44638,44761,45084,45102,45296,45480,45677,45727,46146,46245,46454,46480,46696,46789,47181,47252,47446,47613,47816,47842,48183,48282,48599,48698,48899,49001,49339,49344,49542,49760,49966,50016,50404,50523,50750,50797,51070,51172,51513,51566,51773,51984,52202,52217,52636,52740,52952,53044,53250,53357,53902,53929,54141,54338,54553,54615,54977,55114,55345,55352,55567,55673,56035,56083,56370,56552,56809,56835,57244,57352,57573,57695,57955,58068,58436,58448,58669,58932,59213,59267,59644,59764,59989,60033,60257,60409,60852,60909,61180,61368,61596,61604,62092,62200,62437,62547,62775,62891,63271,63315,63545,63742,63975,64035,64533,64650,64949,64972,65200,65316,65834,65891,66121,66407,66644,66674,67075,67192,67432,67530,67845,67985,68451,68451,68690,68896,69138,69222,69644,69778,70021,70083,70382,70493,71050,71112,71355,71558,71806,71820,72287,72452,72700,72822,73068,73193,73603,73635,73988,74223,74493,74556,74978,75106,75402,75419,75670,75795,76290,76350,76602,76814,77140,77166,77597,77758,78015,78152,78403,78574,79002,79019,79271,79504,79764,79827,80576,80707,80970,81023,81280,81409,81846,81927,82188,82446,82736,82741,83199,83330,83669,83785,84049,84184,84701,84733,85042,85329,85640,85708,86160,86295,86565,86596,86950,87101,87553,87619,87880,88155,88428,88470,89019,89150,89437,89550,89823,89961,90569,90578,90916,91179,91457,91520,92032,92209,92488,92550,92823,92961,93506,93589,93957,94187,94469,94487,94963,95098,95383,95563,95845,95988,96599,96637,96921,97163,97529,97601,98140,98284,98580,98582,98869,99087,99569,99640,99928,100218,100524,100559,101182,101326,101649,101765,102121,102279,102855,102879,103167,103418,103714,103786,104283,104433,104813,104899,105190,105337,105828,105903,106200,106556,106867,106873,107442,107591,107947,108078,108498,108657,109160,109196,109498,109800,110105,110201,110713,110892,111200,111232,111588,111740,112485,112556,112862,113119,113428,113467,114075,114281,114592,114752,115061,115219,115737,115740,116153,116419,116734,116838,117495,117653,117968,118051,118363,118519,119046,119126,119432,119745,120235,120253,120789,120938,121283,121420,121738,121942,122613,122654,122974,123291,123614,123697,124389,124551,124875,124896,125214,125375,125917,126028,126423,126689,127024,127063,127683,127880,128297,128434,128761,128926,129474,129497,129826,130241,130573,130650,131222,131389,131722,131790,132225,132386,133177,133261,133647,133925,134263,134266,134874,135041,135398,135555,135887,136087,136848,136889,137222,137509,137850,137936,138579,138792,139134,139175,139591,139761,140327,140411,140860,141201,141546,141591,142172,142343,142697,142918,143254,143428,144098,144107,144454,144762,145274,145360,145947,146123,146533,146615,146965,147198,147785,147875,148226,148519,148902,148925,149819,150040,150396,150548,150898,151092,151685,151741,152097,152434,152794,152884,153591,153771,154232,154240,154624,154798,155496,155585,155941,156363,156726,156781,157455,157631,157996,158180,158656,158839,159438,159459,159824,160135,160569,160689,161383,161568,161937,162014,162377,162556,163383,163484,163906,164322,164694,164706,165332,165578,165953,166114,166486,166674,167409,167451,168020,168337,168726,168821,169468,169657,170073,170131,170508,170691,171323,171445,171823,172137,172620,172668,173390,173579,173962,174117,174498,174743,175549,175549,175923,176345,176738,176833,177690,177885,178272,178358,178744,178983,179779,179902,180285,180608,180998,181016,181672,181866,182367,182551,183063,183260,183913,183963,184355,184774,185169,185268,186053,186262,186660,186686,187202,187418,188080,188173,188569,188961,189360,189431,190114,190308,190781,190948,191347,191550,192527,192553,192949,193290,193709,193808,194485,194802,195215,195314,195773,195974,196729,196831,197386,197724,198132,198137,199067,199265,199675,199893,200301,200507,201187,201237,201647,202035,202563,202682,203374,203601,204015,204062,204457,204730,205548,205650,206064,206405,206896,206949,207842,208049,208469,208680,209097,209315,210013,210028,210510,210929,211351,211455,212248,212460,213069,213161,213583,213789,214490,214597,215109,215654,216082,216109,216825,217037,217477,217674,218231,218446,219269,219331,219754,220116,220572,220709,221431,221662,222094,222101,222532,222747,223844,223950,224378,224740,225219,225267,226166,226453,226890,227072,227503,227760,228488,228514,229084,229493,229933,230041,230838,231059,231515,231637,232170,232430,233281,233394,233835,234203,234770,234782,235540,235761,236207,236470,236910,237191,237934,237988,238434,238811,239261,239381,240589,240814,241344,241388,241837,242061,242813,242965,243411,243854,244318,244375,245178,245449,246031,246219,246672,246900,247810,247818,248273,248761,249256,249364,250266,250503,250962,251072,251678,251906,252673,252789,253248,253628,254090,254134,255009,255239,255745,255942,256404,256637,257668,257728,258189,258687,259238,259355,260152,260451,260939,260962,261429,261657,262559,262675,263286,263804,264277,264334,265125,265355,265828,266114,266581,266818,267606,267636,268244,268645,269254,269371,270346,270586,271092,271190,271735,272050,272838,272978,273455,273921,274401,274401,275429,275668,276150,276356,276832,277074,278153,278237,278719,279141,279626,279760,280572,280815,281433,281495,281980,282279,283091,283202,283688,284245,284734,284796,285715,285958,286449,286652,287398,287646,288632,288646,289132,289599,290094,290259,291086,291334,291829,291951,292445,292691,293984,294109,294595,295005,295503,295535,296371,296724,297324,297559,298116,298386,299216,299279,299930,300352,300862,300990,301939,302235,302750,302767,303265,303516,304358,304483,305058,305553,306203,306263,307267,307519,308029,308241,308813,309139,310115,310141,310650,311081,311612,311773,312864,313121,313634,313771,314281,314532,315389,315560,316073,316501,317106,317123,318154,318406,319069,319302,319818,320078,320941,321004,321517,322266,322841,322972,323844,324107,324637,324690,325368,325625,326676,326805,327434,327871,328396,328477,329358,329619,330189,330447,330968,331258,332424,332429,332956,333414,333956,334087,335087,335426,335959,336075,336600,336864,337967,338102,338807,339324,339858,339890,340873,341182,341718,342005,342539,342850,343903,343971,344507,344959,345645,345780,346682,346952,347492,347523,348173,348527,349423,349574,350106,350558,351101,351167,352602,352863,353408,353683,354226,354499,355404,355446,356052,356601,357149,357280,358197,358484,359407,359520,360063,360336,361391,361529,362074,362682,363234,363243,364169,364507,365076,365339,366058,366336,367256,367319,367873,368385,368942,369119,370414,370693,371251,371313,371870,372143,373375,373513,374071,374616,375219,375302,376243,376611,377174,377404,378042,378324,379402,379420,380178,380654,381322,381457,382404,382689,383256,383436,383999,384281,385222,385365,385928,386539,387343,387381,388456,388740,389312,389554,390115,390481,391434,391506,392195,392734,393309,393453,394685,394981,395559,395561,396131,396418,397692,397910,398557,399039,399618,399689,400672,400960,401700,401990,402569,402875,404071,404106,404687,405310,405895,406039,407141,407464,408049,408165,408924,409280,410257,410415,410996,411572,412160,412184,413170,413458,414048,414299,415005,415301,416733,416805,417476,417973,418566,418716,419768,420148,420742,420828,421416,421707,422789,422936,423709,424200,424823,424898,426115,426412,427113,427469,428066,428377,429372,429378,429977,430546,431317,431466,432488,432844,433447,433578,434180,434600,435757,435916,436519,437022,437687,437723,439309,439611,440219,440521,441127,441432,442445,442541,443135,443647,444258,444437,445590,445898,446683,446715,447399,447755,448771,448923,449535,450280,451005,451076,452107,452413,453067,453324,454149,454458,455670,455709,456323,456931,457558,457764,458906,459217,459840,460000,460620,460929,462296,462454,463200,463718,464342,464345,465519,465932,466558,466824,467448,467763,468806,468910,469723,470380,471024,471182,472279,472594,473277,473360,473988,474300,475718,475874,476500,477027,477839,477919,478980,479286,479987,480300,480933,481423,482478,482496,483131,483667,484305,484454,486093,486438,487085,487222,488025,488343,489410,489614,490253,490924,491586,491627,492703,493023,493878,494195,494833,495156,496387,496470,497114,497806,498453,498615,499784,500108,500872,500893,501813,502131,503213,503374,504022,504564,505217,505328,506560,506955,507633,507899,508550,508885,510321,510360,511008,511628,512284,512481,513773,514190,514858,514995,515651,515978,517265,517430,518284,518832,519492,519515,520621,520950,521642,522057,522713,523045,524346,524423,525080,525652,526749,526916,528171,528504,529185,529253,529918,530353,531465,531626,532288,533079,533748,533832,535262,535648,536319,536597,537266,537604,538886,538889,539695,540303,540978,541145,542272,542629,543495,543652,544326,544658,545785,545985,546736,547497,548183,548224,549600,549933,550613,550900,551800,552141,553502,553588,554347,554990,555685,555898,557040,557382,558066,558107,558781,559197,560860,561030,561785,562351,563038,563122,564315,564764,565454,565795,566619,566964,568112,568157,569051,569632,570396,570567,571871,572225,572918,573139,573866,574202,575359,575533,576222,576892,577780,577789,578955,579302,580123,580431,581127,581639,583150,583236,583929,584516,585217,585393,586895,587305,588007,588089,588790,589140,590306,590539,591241,591828,592533,592623,594374,594725,595631,595924,596611,596994,598169,598192,598899,599793,600546,600767,601954,602310,603023,603175,604096,604446,605807,606001,606712,607305,608147,608203,609411,609767,610483,610820,611617,611977,613560,613650,614366,615073,615793,615973,617425,617886,618680,618688,619404,619788,620990,621164,622258,622956,623708,623797,625008,625364,626089,626511,627234,627597,629033,629088,629808,630482,631415,631591,632808,633173,633922,634106,634829,635305,636798,636981,637710,638309,639041,639062,640956,641321,642112,642423,643250,643684,644907,645027,645756,646450,647194,647379,648626,648995,649942,650019,650903,651266,652720,652899,653637,654464,655220,655321,656562,656984,657727,658143,659105,659477,660715,660727,661465,662091,662837,663083,664489,664864,665745,665906,666652,667024,668796,668984,669731,670466,671216,671258,672616,673185,673937,674254,675000,675389,676824,676919,677917,678564,679319,679508,680995,681411,682209,682267,683022,683399,684661,684844,685671,686303,687276,687398,688906,689284,690045,690359,691118,691601,692869,692917,693777,694499,695395,695584,697221,697604,698369,698524,699283,699664,701127,701372,702133,702939,703772,703772,705058,705432,706419,706841,707609,708002,709282,709377,710303,711160,711952,712147,713606,713993,714767,714853,715881,716267,717553,717792,718566,719362,720219,720342,721643,722026,722820,723143,723997,724387,726717,726735,727514,728170,728952,729146,730468,730969,731752,731936,732718,733230,734537,734734,735829,736482,737270,737320,738807,739199,739987,740406,741347,741742,743055,743154,743937,744722,745819,746028,747485,747883,748675,748701,749492,750008,751569,751785,752573,753235,754038,754131,755834,756230,757171,757563,758345,758744,760072,760143,760940,761623,762423,762617,764228,764701,765724,765891,766691,767090,768637,768840,769641,770618,771422,771448,773028,773424,774314,774655,775698,776117,777654,777753,778559,779236,780046,780363,781715,782128,782949,783048,783857,784316,786088,786289,787095,787850,788809,788911,790449,791004,791826,792164,792973,793381,794730,794735,795791,796721,797539,797737,799104,799514,800359,800577,801560,801968,803611,803817,804797,805477,806532,806582,808021,808431,809256,809644,810463,810991,812364,812483,813386,814078,814905,815132,817203,817617,818445,818492,819356,819751,821439,821712,822540,823358,824191,824293,825684,826098,827166,827507,828338,828829,830571,830624,831448,832341,833189,833396,834793,835213,836121,836332,837603,838020,839411,839629,840466,841164,842004,842019,843713,844195,845037,845456,846292,846714,848555,848659,849496,850289,851134,851346,852758,853367,854362,854454,855294,855716,857332,857538,858743,859444,860346,860453,861886,862398,863249,863794,864643,865071,866489,866516,867367,868083,869169,869381,871456,871896,872789,872986,873840,874397,875824,876039,876890,877713,878571,878633,880471,880894,881773,882135,882993,883449,885137,885274,886134,886856,888001,888232,889719,890151,891345,891352,892210,892641,894083,894298,895162,896259,897126,897232,898872,899300,900170,900532,901656,902135,903583,903631,904671,905570,906515,906802,908346,908783,909664,909846,910715,911146,913268,913525,914398,915126,916004,916030,917649,918219,919097,919506,920382,920822,922603,922711,923874,924671,925552,925773,927524,927980,928862,928984,929860,930393,931859,932119,933001,933852,934988,935101,936582,937023,937922,938290,939387,939954,941644,941656,942640,943398,944288,944509,946416,946862,947842,948105,948995,949435,950916,951197,952088,952831,953725,953779,955463,955909,957357,957734,958628,959078,960571,960691,961587,962795,963695,963920,965482,966012,966912,966956,968156,968605,970377,970601,971483,972235,973158,973310,975094,975540,976445,976888,977904,978368,980476,980533,981438,982241,983179,983450,985164,985746,986655,986843,987742,988195,989712,989940,991118,992028,993101,993109,994635,995090,996005,996493,997405,997900,999641,999749,1000663,1001565,1002741,1002978,1004525,1004984,1005902,1006012,1007014,1007620,1009398,1009626,1010723,1011490,1012413,1012529,1014854,1015313,1016236,1016616,1017638,1018100,1019638,1019682,1020587,1021462,1022388,1022618,1024165,1024671,1025861,1026058,1026984,1027446,1029518,1029751,1030678,1031709,1032665,1032725,1034281,1034742,1035681,1036179,1037409,1037960,1039513,1039630,1040679,1041476,1042448,1042747,1044512,1045000,1045938,1045961,1047079,1047546,1049618,1049846,1050778,1051680,1052619,1052735,1054318,1054929,1055949,1056467,1057402,1057875,1059869,1059926,1061144,1061935,1062880,1063110,1064687,1065160,1066275,1066561,1067505,1067972,1069546,1069783,1070719,1071507,1072861,1072891,1074684,1075292,1076242,1076643,1077587,1078196,1079770,1079887,1080918,1081893,1082846,1083086,1085536,1086042,1086996,1087094,1088042,1088587,1090407,1090722,1091676,1092464,1093421,1093561,1095294,1095771,1096997,1097463,1098420,1098900,1100498,1100498,1101452,1102480,1103616,1103855,1105945,1106427,1107401,1107607,1108852,1109328,1110935,1111177,1112229,1113308,1114289,1114373,1115989,1116471,1117439,1117861,1118823,1119308,1121662,1121796,1122989,1123801,1124779,1125022,1126644,1127262,1128234,1128296,1129267,1129752,1131368,1131667,1132957,1133769,1134827,1134938,1136783,1137269,1138348,1138905,1139876,1140365,1142341,1142403,1143380,1144299,1145556,1145799,1147481,1147972,1148955,1149158,1150138,1150884,1152815,1153063,1154044,1155030,1156058,1156072,1158177,1158663,1159674,1160141,1161316,1161811,1163454,1163619,1164605,1165432,1166478,1166726,1168593,1169088,1170354,1170476,1171588,1172082,1173734,1173980,1175060,1176353,1177346,1177471,1179132,1179618,1180793,1181203,1182489,1182987,1184933,1184965,1185960,1186796,1187794,1188147,1189814,1190414,1191413,1191648,1192628,1193185,1195362,1195632,1196627,1197457,1198459,1198522,1200894,1201545,1202564,1202986,1203988,1204498,1206429,1206557,1207856,1208805,1209812,1210108,1211805,1212320,1213328,1213345,1214352,1214850,1216921,1217172,1218180,1219022,1220605,1220730,1222523,1223098,1224111,1224606,1225613,1226263,1227948,1228008,1229016,1230020,1231036,1231288,1233873,1234383,1235400,1235612,1236628,1237200,1238891,1239217,1240548,1241524,1242544,1242570,1244276,1244785,1246096,1246527,1247538,1248069,1250076,1250237,1251259,1252350,1253375,1253632,1255344,1255857,1256885,1257022,1258455,1258965,1261043,1261294,1262320,1263177,1264214,1264385,1266324,1266837,1267898,1268326,1269355,1269960,1272206,1272223,1273254,1274285,1275421,1275673,1277400,1278063,1279163,1279396,1280631,1281147,1283120,1283380,1284745,1285608,1286646,1286709,1288487,1289000,1290052,1290801,1291922,1292497,1294221,1294352,1295392,1296264,1297602,1297865,1299953,1300483,1301843,1301896,1302934,1303612,1305354,1305611,1306655,1307706,1308753,1308882,1311443,1312072,1313163,1313600,1314647,1315172,1317168,1317249,1318298,1319179,1320231,1320492,1322564,1323134,1324486,1324744,1325794,1326315,1328072,1328362,1329411,1330577,1331635,1331640,1333637,1334164,1335222,1335680,1337126,1337668,1339431,1339562,1340611,1341611,1342864,1343203,1345125,1345658,1346830,1346946,1348007,1348532,1351249,1351513,1352575,1353678,1354754,1354889,1356670,1357375,1358442,1358959,1360020,1360554,1362329,1362361,1363983,1364966,1366036,1366345,1368365,1368901,1369974,1370261,1371331,1371865,1373652,1373963,1375034,1376087,1377466,1377534,1379342,1379878,1380997,1381449,1382654,1383340,1385745,1385880,1386947,1387849,1389016,1389286,1391598,1392138,1393218,1393249,1394415,1395065,1396987,1397341,1398417,1399313,1400396,1400547,1402718,1403250,1404737,1405189,1406481,1407024,1408829,1408895,1409980,1411415,1412510,1412771,1414588,1415133,1416222,1416497,1417930,1418473,1420758,1421031,1422120,1423025,1424146,1424188,1426014,1426620,1427906,1428455,1429547,1430095,1432476,1432607,1433816,1434733,1435855,1436142,1438204,1439127,1440225,1440338,1441430,1441973,1443805,1444078,1445499,1446554,1447657,1447795,1449969,1450514,1451617,1452225,1453322,1453874,1456040,1456049,1457347,1458273,1459692,1460030,1461877,1462446,1463561,1463824,1464930,1465649,1467490,1467768,1468875,1469795,1471105,1471168,1473980,1474534,1475646,1476158,1477264,1477821,1479932,1480109,1481221,1482516,1483631,1483910,1485772,1486330,1487754,1487816,1488926,1489483,1491609,1491882,1493213,1494445,1495680,1495818,1497701,1498259,1499399,1499944,1501429,1502032,1503900,1503983,1505101,1506042,1507167,1507535,1509769,1510332,1511457,1511687,1512811,1513449,1516301,1516583,1517704,1518782,1519981,1519999,1521948,1522706,1523836,1524312,1525559,1526227,1528428,1528563,1530024,1530971,1532104,1532389,1534476,1535043,1536177,1536357,1537714,1538277,1540169,1540451,1541581,1542522,1543982,1544125,1546275,1546838,1547978,1548589,1549726,1550530,1552428,1552466,1553605,1554680,1555834,1556118,1558559,1559131,1560480,1560722,1561864,1562425,1564674,1565040,1566272,1567225,1568413,1568485,1570401,1571090,1572862,1573401,1574547,1575122,1577035,1577179,1578322,1579554,1580705,1581001,1583739,1584317,1585495,1585497,1586985,1587555,1589468,1589755,1590903,1592177,1593332,1593550,1595523,1596170,1597327,1597809,1598960,1599539,1602453,1602524,1603681,1604664,1606034,1606322,1608259,1608999,1610162,1610452,1611753,1612332,1614269,1614575,1616077,1617273,1618457,1618492,1620976,1621557,1622730,1623353,1624517,1625102,1627042,1627186,1628577,1629679,1631175,1631498,1633450,1634035,1635205,1635321,1636490,1637249,1639477,1639833,1640997,1641974,1643185,1643343,1645856,1646437,1647685,1648261,1649430,1650018,1652582,1652606,1653781,1654767,1655999,1656287,1658511,1659101,1660615,1660866,1662026,1662732,1664699,1664995,1666263,1667695,1668978,1669050,1671026,1671697,1672882,1673379,1675178,1675771,1678136,1678286,1679465,1680517,1681704,1682084,1684081,1684675,1685863,1685949,1687136,1687724,1690306,1690597,1691928,1693010,1694216,1694363,1696615,1697388,1698797,1699288,1700479,1701102,1703090,1703165,1704743,1705960,1707156,1707453,1709450,1710151,1711348,1711704,1713003,1713600,1715926,1716237,1717559,1718554,1720095,1720101,1722470,1723069,1724271,1724840,1726036,1726807,1728810,1728959,1730161,1731183,1732511,1732867,1735911,1736514,1737722,1737853,1739058,1739660,1741666,1742086,1743292,1744449,1745876,1746035,1748143,1748746,1750300,1750803,1752012,1752677,1754979,1755015,1756221,1757807,1759022,1759324,1761396,1762004,1763248,1763550,1765119,1765725,1768022,1768327,1769814,1770827,1772056,1772152,1774714,1775308,1776528,1777040,1778258,1778869,1781652,1781831,1783051,1784204,1785427,1785735,1787777,1788562,1789794,1789826,1791044,1791728,1794618,1794974,1796557,1797573,1798800,1798952,1801003,1801615,1802859,1803604,1804827,1805552,1807600,1807671,1808897,1809928,1811610,1811916,1814240,1814894,1816255,1816512,1818095,1818920,1820977,1821286,1822515,1823727,1824965,1825004,1827652,1828266,1829504,1830112,1831348,1831975,1834328,1834534,1835767,1836909,1838150,1838461,1840533,1841156,1843132,1843292,1844533,1845153,1847207,1847516,1848865,1850232,1851477,1851635,1854115,1854861,1856108,1856626,1858395,1859019,1861097,1861100,1862347,1863521,1864771,1865184,1867646,1868272,1869625,1869891,1871232,1871856,1874896,1875211,1876458,1877501,1878755,1878859,1880967,1881780,1883036,1883693,1884943,1885587,1887680,1887838,1889461,1890558,1892039,1892354,1894731,1895414,1896674,1896757,1898016,1898644,1901052,1901364,1902620,1904038,1905655,1905811,1907922,1908548,1909813,1910340,1911603,1912415,1914896,1914976,1916484,1917545,1918892,1919198,1922245,1922946,1924226,1924539,1925802,1926435,1928552,1929042,1930311,1931366,1932638,1932656,1935054,1935689,1937320,1937856,1939223,1939861,1942422,1942571,1943998,1945637,1946944,1947289,1949436,1950083,1951361,1951498,1953148,1953951,1956383,1956701,1957979,1959046,1960329,1960533,1962737,1963376,1964666,1965337,1966863,1967525,1970311,1970352,1971626,1972702,1974097,1974417,1976982,1977837,1979177,1979494,1980780,1981418,1983559,1983882,1985546,1986777,1988201,1988284,1990572,1991216,1992742,1993434,1994706,1995353,1997808,1997970,1999262,2000431,2002089,2002413,2004575,2005339,2006637,2006658,2007953,2008873,2011035,2011353,2012649,2013731,2015030,2015191,2018922,2019570,2020871,2021413,2022712,2023365,2025530,2025641,2027075,2028307,2029626,2030021,2032423,2033101,2034880,2035146,2036497,2037148,2039871,2040206,2041495,2042931,2044475,2044514,2046700,2047348,2048658,2049278,2050969,2051625,2053805,2054002,2055307,2056599,2057912,2058329,2060808,2061476,2062873,2063010,2064318,2064974,2067826,2068153,2069729,2071016,2072333,2072498,2074699,2075553,2077004,2077552,2078869,2079529,2082240,2082263,2083967,2085073,2086402,2086731,2089025,2089717,2091040,2091455,2092777,2093433,2096096,2096428,2097751,2099052,2100750,2100827,2103475,2104132,2105460,2106032,2107358,2108455,2110668,2110835,2112158,2113413,2114744,2115077,2117926,2118607,2119977,2120045,2121790,2122455,2125036,2125471,2126803,2127915,2129250,2129411,2131642,2132304,2134020,2134811,2136356,2137025,2139250,2139334,2140770,2142200,2143540,2143926,2146456,2147127,2148701,2148979,2150757,2151426,2153663,2154001,2155342,2156624,2157968,2157971,2160229,2161035,2162393,2163001,2164341,2165016,2168777,2168944,2170290,2171417,2172767,2173124,2175781,2176647,2178041,2178198,2179542,2180216,2182468,2182800,2184570,2185697,2187050,2187250,2189808,2190559,2192029,2192790,2194143,2194829,2197084,2197125,2198480,2199856,2202006,2202339,2204666,2205346,2206705,2206992,2208336,2209236,2211970,2212311,2213831,2215192,2216554,2216640,2219558,2220317,2221682,2222325,2223687,2224382,2226655,2226868,2228493,2229635,2231002,2231344,2234077,2234761,2236518,2236559,2237923,2238597,2240879,2241295,2242659,2244322,2245752,2245922,2248405,2249160,2250533,2251099,2252871,2253558,2256626,2256710,2258078,2259271,2260791,2261240,2263537,2264227,2265604,2265945,2267321,2268145,2271189,2271534,2272911,2274059,2275447,2275492,2278101,2278995,2280396,2280977,2282659,2283423,2285726,2285897,2287789,2289093,2290478,2290832,2293144,2293837,2295225,2295446,2296831,2297558,2300284,2300620,2302006,2303163,2305110,2305284,2307839,2308528,2310171,2310841,2312230,2313118,2315436,2315445,2316933,2318099,2319494,2319841,2323344,2324165,2325560,2325868,2327260,2327956,2330283,2330795,2332181,2333692,2335090,2335176,2337935,2338628,2340421,2341008,2342406,2343107,2345818,2345994,2347389,2348891,2350294,2350704,2353151,2353853,2355403,2355485,2357323,2358024,2360366,2360716,2362263,2363429,2365224,2365457,2368264,2368966,2370376,2370963,2372362,2373067,2376123,2376213,2377622,2379373,2380822,2381173,2383545,2384451,2385864,2386157,2387569,2388256,2390943,2391326,2393554,2394729,2396160,2396183,2398549,2399256,2400674,2401568,2403151,2403904,2406264,2406485,2407898,2409085,2410909,2411265,2413948,2414661,2416094,2416246,2417667,2418588,2421635,2421985,2423407,2424768,2426213,2426407,2429460,2430171,2431598,2432191,2433612,2434454,2437414,2437470,2438892,2440100,2441555,2441911,2444448,2445164,2446997,2447334,2449037,2449834,2452557,2452917,2454348,2455931,2457365,2457455,2460157,2460873,2462375,2463082,2464935,2465655,2468048,2468228,2469664,2471116,2472597,2473058,2475460,2476254,2477954,2477962,2479546,2480262,2483761,2484145,2485581,2486783,2488226,2488400,2490811,2491905,2493350,2494048,2495491,2496243,2498648,2498737,2500791,2502002,2503462,2503818,2507180,2507905,2509354,2509776,2511219,2511942,2514359,2514722,2516167,2517603,2519577,2519632,2522058,2522778,2524320,2524994,2526446,2527379,2530140,2530316,2531770,2532987,2534708,2535073,2538189,2538938,2540519,2540703,2542160,2542883,2545315,2545791,2547245,2548738,2550348,2550531,2553293,2554022,2555900,2556499,2558061,2558793,2561231,2561252,2563030,2564924,2566390,2566755,2569202,2569993,2571460,2571771,2573744,2574571,2577448,2577882,2579349,2580572,2582042,2582162,2584618,2585347,2586819,2587513,2588974,2589718,2593452,2593637,2595109,2596356,2597831,2598200,2601550,2602497,2603975,2604052,2605648,2606532,2608988,2609351,2611258,2612712,2614191,2614370,2616853,2617591,2619072,2619899,2621659,2622415,2625227,2625328,2626908,2628149,2630050,2630472,2632949,2633692,2635203,2635619,2637100,2638062,2640539,2640911,2642378,2643616,2645104,2645116,2649042,2649780,2651738,2652364,2653848,2654594,2657068,2657314,2658801,2660207,2661827,2662202,2664694,2665575,2667494,2667655,2669143,2669889,2672729,2673101,2674595,2676367,2677872,2678060,2681059,2681806,2683362,2684097,2686031,2686781,2689567,2689609,2691108,2692466,2693968,2694537,2697371,2698123,2699626,2699943,2701622,2702368,2705625,2706014,2707517,2708952,2710727,2710822,2713380,2714378,2715886,2716533,2718039,2718794,2721755,2721944,2724050,2725537,2727048,2727464,2730046,2730844,2732376,2732434,2733940,2734695,2737211,2737588,2739387,2740649,2742595,2742778,2745642,2746469,2747993,2748625,2750136,2751109,2753985,2754107,2755624,2757132,2758652,2759030,2762287,2763048,2764571,2764885,2766405,2767164,2770571,2771054,2772700,2773968,2775503,2775551,2778109,2778969,2781041,2781763,2783283,2784179,2787040,2787229,2788755,2790392,2791936,2792319,2795361,2796126,2797656,2797811,2800135,2800894,2803446,2803827,2805599,2807062,2808639,2808884,2811547,2812308,2813843,2814649,2816182,2817015,2820739,2820739,2822271,2823557,2825095,2825469,2828036,2829023,2830840,2831262,2832795,2833563,2836127,2836520,2838508,2839788,2841330,2841425,2844340,2845266,2846811,2847668,2849365,2850157,2852730,2852925,2854464,2855923,2858262,2858649,2861693,2862467,2864015,2864101,2865648,2866676,2869774,2870160,2871708,2872994,2874547,2874786,2878109,2878883,2880436,2881232,2882779,2883636,2886224,2886347,2887895,2889196,2891028,2891411,2894349,2895143,2897143,2897466,2899022,2899876,2902467,2902857,2904414,2906744,2908304,2908322,2911201,2911980,2913675,2914331,2916397,2917179,2920144,2920338,2922197,2923519,2925156,2925657,2928314,2929097,2930678,2930862,2932427,2933209,2936601,2937113,2938675,2939982,2941616,2941813,2945092,2946187,2947795,2948448,2950118,2950906,2954052,2954102,2956130,2957617,2959192,2959584,2962211,2962999,2964735,2965154,2966728,2967669,2970662,2971057,2972623,2973936,2975963,2976062,2978920,2979703,2981283,2982068,2983945,2985042,2987672,2987881,2989461,2990918,2992501,2992899,2996861,2997653,2999266,2999292,3000858,3001649,3004291,3004807,3006391,3007952,3009539,3009755,3012469,3013257,3015703,3016365,3018137,3018940,3022060,3022153,3023742,3025445,3027037,3027433,3030105,3031046,3032740,3033132,3035187,3035969,3038620,3039019,3040612,3041940,3043668,3043739,3047479,3048276,3049874,3050557,3052153,3052953,3056486,3056680,3058273,3059884,3061497,3061970,3064642,3065665,3067267,3067434,3069035,3069835,3073182,3073581,3075729,3077276,3079171,3079374,3082055,3082856,3084463,3085440,3087041,3087845,3090523,3090549,3092156,3093736,3095803,3096199,3099399,3100289,3101902,3102243,3103853,3104896,3107583,3108002,3110074,3111611,3113233,3113332,3116787,3117593,3119263,3119940,3121685,3122495,3125562,3125879,3127684,3129036,3130656,3131069,3133771,3134592,3136673,3136772,3138386,3139195,3142443,3142902,3144513,3146285,3147908,3148109,3151170,3151976,3153644,3154399,3156495,3157454,3160156,3160258,3161883,3163421,3165049,3165604,3168321,3169143,3170846,3171184,3173157,3173966,3178439,3178847,3180476,3181825,3183627,3183632,3186358,3187414,3189090,3190020,3191652,3192470,3195193,3195391,3197559,3198926,3200563,3200973,3204062,3204907,3206841,3207059,3208693,3209676,3212708,3213116,3214754,3216397,3218500,3218706,3221447,3222427,3224089,3224769,3226406,3227461,3230579,3230629,3232267,3233706,3235382,3235792,3240405,3241230,3242877,3243265,3245074,3245893,3248634,3249162,3250809,3252182,3253870,3253989,3257273,3258176,3260293,3260985,3262631,3263458,3266208,3266435,3268087,3270158,3272113,3272527,3275289,3276117,3277775,3277822,3279958,3280822,3283968,3284363,3286019,3287707,3289366,3289639,3292497,3293325,3295160,3295978,3297750,3298583,3302179,3302281,3304371,3305762,3307427,3307841,3310981,3312049,3313857,3314198,3315862,3316693,3319470,3319961,3322136,3323878,3325546,3325599,3328385,3329209,3330879,3331772,3333436,3334284,3338213,3338420,3340090,3341487,3343713,3344133,3346925,3347833,3349507,3349718,3351646,3352917,3355709,3356126,3357796,3359187,3360875,3361093,3365282,3366119,3367813,3368511,3370522,3371362,3374160,3374175,3375854,3377548,3379230,3379712,3382753,3383595,3385757,3386176,3387911,3388747,3391944,3392366,3394049,3395890,3397678,3397782,3400598,3401435,3403429,3404222,3406399,3407244,3410435,3410647,3412317,3413729,3415420,3416029,3419389,3420384,3422084,3422176,3423867,3424707,3428504,3428926,3430618,3432234,3433929,3434135,3437479,3438684,3440381,3441082,3442768,3443670,3446890,3446997,3449187,3450620,3452465,3452977,3455814,3456665,3458368,3458913,3460608,3461457,3464294,3464722,3466620,3468038,3470716,3470743,3473957,3474808,3476514,3477230,3478934,3480020,3482860,3483072,3484773,3486848,3488558,3488998,3493020,3493913,3495694,3495891,3497600,3498454,3501811,3502368,3504440,3505867,3507580,3507795,3510656,3511507,3513709,3514532,3516241,3517099,3519948,3520010,3521894,3523732,3525630,3526053,3529297,3530176,3531895,3532257,3534500,3535358,3538801,3539257,3540972,3542660,3544382,3544519,3547395,3548255,3549980,3550702,3552424,3553569,3557759,3557990,3559831,3561318,3563045,3563477,3566374,3567568,3569307,3569314,3571368,3572226,3575102,3575533,3577764,3579206,3580979,3581194,3585021,3585885,3587727,3588824,3590555,3591422,3594658,3594764,3596483,3598123,3600352,3600780,3603677,3604547,3606598,3606960,3608693,3609817,3613163,3613642,3615379,3616827,3618567,3618615,3622340,3623380,3625122,3626021,3627757,3628702,3631605,3631892,3633634,3635178,3636923,3637360,3641424,3642305,3644863,3645045,3646790,3647659,3650571,3651002,3652855,3654977,3656726,3656983,3659916,3660789,3662547,3663275,3665720,3666598,3670036,3670062,3671813,3673432,3675495,3676065,3678992,3679870,3681625,3682034,3683927,3684803,3688600,3689040,3690791,3692572,3694410,3694518,3697841,3699004,3700764,3701561,3703515,3704396,3707326,3707547,3710222,3711973,3713761,3714217,3717159,3718041,3719805,3719927,3721685,3722561,3725911,3726444,3728204,3729670,3731940,3732200,3735151,3736033,3737949,3738800,3740563,3741699,3745235,3745348,3747117,3748598,3750370,3750811,3755281,3756180,3757973,3758341,3760113,3761210,3764563,3765130,3766903,3768593,3770371,3770383,3773349,3774333,3776616,3777374,3779485,3780375,3783953,3784174,3785934,3787841,3789695,3790141,3793113,3794093,3795875,3796138,3798501,3799391,3802357,3802797,3804686,3806167,3807952,3808233,3811912,3812803,3814914,3815657,3817438,3818332,3822198,3822252,3824246,3825930,3827727,3828173,3831295,3832743,3834549,3834926,3836713,3837607,3841296,3841746,3844058,3845551,3847345,3847465,3850995,3851891,3853687,3854895,3856689,3857589,3860582,3860807,3862603,3864165,3866471,3867001,3870396,3871296,3873096,3873140,3874939,3876139,3879141,3879590,3881510,3883282,3885843,3886067,3889930,3890812,3892629,3893381,3895184,3896107,3899583,3899735,3901540,3903324,3905175,3905621,3908638,3909543,3911862,3912305,3914104,3915120,3918137,3918601,3920751,3922859,3924671,3924728,3928330,3929235,3931050,3931853,3934192,3935130,3938153,3938424,3940353,3942067,3943903,3944485,3947832,3948741,3950585,3950773,3952585,3953484,3958874,3959327,3961324,3962841,3964664,3964892,3967933,3969111,3971018,3971928,3973749,3974822,3977860,3977868,3980246,3981772,3983713,3984168,3987616,3988531,3990358,3990846,3993017,3993929,3996961,3997456,3999283,4001024,4003372,4003480,4006536,4007450,4009474,4010376,4012202,4013378,4016975,4017212,4019044,4020591,4022480,4022939,4026871,4027789,4029954,4030064,4032010,4033012,4036434,4037040,4038867,4040645,4042484,4042712,4046181,4047278,4049642,4050409,4052248,4053171,4056239,4056355,4058194,4060519,4062364,4062823,4066455,4067378,4069223,4069603,4072224,4073246,4076749,4077211,4079047,4080585,4082441,4082485,4085763,4086668,4088518,4089393,4091241,4092167,4096300,4096530,4098380,4099927,4102116,4102622,4106305,4107495,4109349,4109546,4111654,4112580,4115672,4116134,4118594,4120666,4122523,4122756,4125899,4126826,4128686,4129717,4131574,4132530,4136414,4136474,4138705,4140261,4142652,4143113,4146235,4147174,4149037,4149535,4151397,4152627,4155734,4156285,4158148,4159701,4161582,4161699,4166347,4167396,4169271,4170068,4171930,4172902,4176633,4176932,4178795,4180560,4182431,4182919,4186041,4186979,4189763,4189786,4191657,4192775,4196447,4196914,4199001,4201073,4202948,4203176};
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    cout << solve[n];
    return 0;
}