#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF (1<<29) #define rep(i,n) for(int i=0;i<(int)(n);i++) #define all(v) v.begin(),v.end() #define uniq(v) v.erase(unique(all(v)),v.end()) #define indexOf(v,x) (find(all(v),x)-v.begin()) #if defined(_MSC_VER)||defined(__SSE4_2__) #include #endif inline int popcount64(unsigned long long x){ #if defined(_MSC_VER) return __popcnt(x>>32)+__popcnt(x); #elif defined(__GNUC__) return __builtin_popcountll(x); #else x = (x>>1 & 0x5555555555555555ULL)+(x & 0x5555555555555555ULL); x = (x>>2 & 0x3333333333333333ULL)+(x & 0x3333333333333333ULL); x = (x>>4 & 0x0f0f0f0f0f0f0f0fULL)+(x & 0x0f0f0f0f0f0f0f0fULL); x = (x>>8 & 0x00ff00ff00ff00ffULL)+(x & 0x00ff00ff00ff00ffULL); x = (x>>16& 0x0000ffff0000ffffULL)+(x & 0x0000ffff0000ffffULL); return ((x>>32)+(x & 0xffffffff)); #endif } long long umekomi[385*2]={ 1,1, 2016542071,134217728, 4179858569,268435456, 6351146542,402653184, 8647178755,536870912, 10819798116,671088640, 13112582219,805306368, 15435178180,939524096, 17783766827,1073741824, 19995222517,1207959552, 22298558097,1342177280, 24671210129,1476395008, 27025469753,1610612736, 29419673939,1744830464, 31867924532,1879048192, 34425213697,2013265920, 36597922058,2147483648, 38891625631,2281701376, 41213834226,2415919104, 43603505547,2550136832, 45958473687,2684354560, 48400385439,2818572288, 50924749040,2952790016, 53293089791,3087007744, 55728829658,3221225472, 58170653878,3355443200, 60697569081,3489660928, 63183433146,3623878656, 65758854595,3758096384, 68442700319,3892314112, 70661484582,4026531840, 72969132463,4160749568, 75271835395,4294967296, 77670276594,4429185024, 80006937100,4563402752, 82439330605,4697620480, 84946429638,4831838208, 87342403410,4966055936, 89751965666,5100273664, 92208054462,5234491392, 94749519875,5368709120, 97211131403,5502926848, 99784395545,5637144576, 102436113901,5771362304, 104834038943,5905580032, 107270116149,6039797760, 109711750702,6174015488, 112238661111,6308233216, 114724570219,6442450944, 117300162543,6576668672, 119984139589,6710886400, 122462777612,6845104128, 125014691055,6979321856, 127634170589,7113539584, 130264415683,7247757312, 132956946308,7381975040, 135675733668,7516192768, 138241056728,7650410496, 140465265264,7784628224, 142776316130,7918845952, 145148534275,8053063680, 147499482149,8187281408, 149910559561,8321499136, 152366833793,8455716864, 154888300991,8589934592, 157211169976,8724152320, 159643294324,8858370048, 162150468133,8992587776, 164635228850,9126805504, 167185535816,9261023232, 169776711171,9395240960, 172359558766,9529458688, 174703885783,9663676416, 177151125559,9797894144, 179661385814,9932111872, 182144512242,10066329600, 184720666574,10200547328, 187296671048,10334765056, 189891036698,10468982784, 192401104118,10603200512, 194982811608,10737418240, 197678486903,10871635968, 200266485344,11005853696, 202974372890,11140071424, 205774323592,11274289152, 208155048164,11408506880, 210586658775,11542724608, 213035163652,11676942336, 215555696869,11811160064, 218060036927,11945377792, 220640220678,12079595520, 223347436431,12213813248, 225780105414,12348030976, 228341866325,12482248704, 230981581406,12616466432, 233605999277,12750684160, 236309167965,12884901888, 239030208489,13019119616, 241672580826,13153337344, 244196748680,13287555072, 246787509975,13421772800, 249456655551,13555990528, 252067337555,13690208256, 254776255621,13824425984, 257608691826,13958643712, 260191183456,14092861440, 262892179649,14227079168, 265681778420,14361296896, 268446156869,14495514624, 271259619702,14629732352, 274171913146,14763950080, 276521441675,14898167808, 278800736335,15032385536, 281114470250,15166603264, 283544884029,15300820992, 285852835570,15435038720, 288283924375,15569256448, 290763748771,15703474176, 293199756432,15837691904, 295581351848,15971909632, 298028104037,16106127360, 300602170446,16240345088, 303040709490,16374562816, 305601134527,16508780544, 308237808535,16642998272, 310678988857,16777216000, 313088582760,16911433728, 315544482879,17045651456, 318086072310,17179869184, 320547859886,17314086912, 323120861173,17448304640, 325772537435,17582522368, 328282611788,17716740096, 330849410482,17850957824, 333437897824,17985175552, 336090631822,18119393280, 338747180679,18253611008, 341480974806,18387828736, 344155541592,18522046464, 346499527149,18656264192, 348946227830,18790481920, 351456846484,18924699648, 353940162160,19058917376, 356516609308,19193135104, 359091718042,19327352832, 361686532100,19461570560, 364196152147,19595788288, 366777957353,19730006016, 369474099733,19864223744, 372062036344,19998441472, 374769985423,20132659200, 377569335023,20266876928, 380081084166,20401094656, 382628039435,20535312384, 385240053763,20669530112, 387877100790,20803747840, 390560526683,20937965568, 393282398741,21072183296, 396015792087,21206401024, 398662931024,21340618752, 401389964696,21474836480, 404188416745,21609054208, 406953341933,21743271936, 409799362270,21877489664, 412648707113,22011707392, 414982515610,22145925120, 417415920338,22280142848, 419920030228,22414360576, 422407558678,22548578304, 424964298081,22682796032, 427549812403,22817013760, 430162455060,22951231488, 432661629018,23085449216, 435232387291,23219666944, 437927773242,23353884672, 440516068395,23488102400, 443212979522,23622320128, 445996903475,23756537856, 448536527790,23890755584, 451104150699,24024973312, 453692236398,24159191040, 456345415402,24293408768, 459000578672,24427626496, 461735174237,24561844224, 464479050991,24696061952, 467115094192,24830279680, 469827406203,24964497408, 472646469342,25098715136, 475380930467,25232932864, 478226828698,25367150592, 481160082435,25501368320, 483608128691,25635586048, 486175479780,25769803776, 488822525399,25904021504, 491443091627,26038239232, 494140462121,26172456960, 496878054426,26306674688, 499572441362,26440892416, 502258684900,26575110144, 504978951149,26709327872, 507764539058,26843545600, 510559467944,26977763328, 513420839485,27111981056, 516239972036,27246198784, 518887028634,27380416512, 521610553228,27514634240, 524411125776,27648851968, 527171730268,27783069696, 530019313303,27917287424, 532938068951,28051505152, 535690699690,28185722880, 538540163469,28319940608, 541483251731,28454158336, 544375470226,28588376064, 547361940036,28722593792, 550225278381,28856811520, 552431041517,28991029248, 554727669221,29125246976, 557084373276,29259464704, 559459305587,29393682432, 561839186032,29527900160, 564284783501,29662117888, 566853429503,29796335616, 569167508599,29930553344, 571588514724,30064771072, 574059188182,30198988800, 576577860148,30333206528, 579088582777,30467424256, 581676679524,30601641984, 584328247525,30735859712, 586648762205,30870077440, 589081292737,31004295168, 591580681943,31138512896, 594071320014,31272730624, 596615205825,31406948352, 599211144408,31541166080, 601835128621,31675383808, 604315857287,31809601536, 606889957436,31943819264, 609570400469,32078036992, 612174376769,32212254720, 614864044320,32346472448, 617639156877,32480690176, 620097194685,32614907904, 622517545445,32749125632, 624972403825,32883343360, 627497010443,33017561088, 629972677602,33151778816, 632548841747,33285996544, 635217857653,33420214272, 637714246142,33554432000, 640267674815,33688649728, 642874013266,33822867456, 645512988221,33957085184, 648190092126,34091302912, 650915905967,34225520640, 653606242405,34359738368, 656111984342,34493956096, 658687379474,34628173824, 661395430381,34762391552, 663967787129,34896609280, 666671284040,35030827008, 669465057593,35165044736, 672108003115,35299262464, 674792114825,35433480192, 677556103806,35567697920, 680314494230,35701915648, 683145157173,35836133376, 686025123273,35970351104, 688576597632,36104568832, 690983419885,36238786560, 693433886325,36373004288, 695982932450,36507222016, 698441455108,36641439744, 701010169220,36775657472, 703658457677,36909875200, 706172636493,37044092928, 708745314059,37178310656, 711328510130,37312528384, 713978535525,37446746112, 716630677540,37580963840, 719367061827,37715181568, 722090104641,37849399296, 724569752176,37983617024, 727144027882,38117834752, 729824064813,38252052480, 732428969549,38386270208, 735118281667,38520487936, 737892684385,38654705664, 740551497237,38788923392, 743248844904,38923141120, 745986457298,39057358848, 748755133674,39191576576, 751597061404,39325794304, 754444883408,39460012032, 757137463386,39594229760, 759673274442,39728447488, 762264136776,39862665216, 764925312743,39996882944, 767540666658,40131100672, 770251054933,40265318400, 773095770910,40399536128, 775663624674,40533753856, 778368775225,40667971584, 781163722659,40802189312, 783915824272,40936407040, 786736748483,41070624768, 789656319354,41204842496, 792328577274,41339060224, 795014454005,41473277952, 797778250150,41607495680, 800536611606,41741713408, 803366994623,41875931136, 806243657141,42010148864, 809063904614,42144366592, 811893354710,42278584320, 814761014195,42412802048, 817667902979,42547019776, 820627453229,42681237504, 823650060126,42815455232, 826195995327,42949672960, 828612440851,43083890688, 831077047597,43218108416, 833597627570,43352326144, 836068832557,43486543872, 838647038463,43620761600, 841310374496,43754979328, 843808447973,43889197056, 846368250656,44023414784, 848966127935,44157632512, 851610921820,44291850240, 854280918759,44426067968, 857008597012,44560285696, 859704793829,44694503424, 862213151388,44828721152, 864780731605,44962938880, 867481363526,45097156608, 870062275305,45231374336, 872762121434,45365592064, 875550051951,45499809792, 878198171106,45634027520, 880885470079,45768245248, 883644514120,45902462976, 886407041817,46036680704, 889237003125,46170898432, 892109534187,46305116160, 894761642004,46439333888, 897309737568,46573551616, 899901725685,46707769344, 902555203259,46841987072, 905190813817,46976204800, 907901932075,47110422528, 910710669981,47244640256, 913303452698,47378857984, 916012702837,47513075712, 918823458017,47647293440, 921559060330,47781511168, 924394097805,47915728896, 927326782087,48049946624, 929966223364,48184164352, 932654264548,48318382080, 935426562441,48452599808, 938189679642,48586817536, 941013717345,48721035264, 943908862437,48855252992, 946710721889,48989470720, 949537429585,49123688448, 952431438722,49257906176, 955327488252,49392123904, 958287695828,49526341632, 961323916125,49660559360, 963924738955,49794777088, 966492737517,49928994816, 969080925079,50063212544, 971734774348,50197430272, 974388247512,50331648000, 977123986647,50465865728, 979867932939,50600083456, 982503823698,50734301184, 985215205279,50868518912, 988034643437,51002736640, 990768335853,51136954368, 993614895574,51271172096, 996557223110,51405389824, 999145398059,51539607552 }; int main(){ /*long long n,s=0,p=1,c=1; n=1000000000000; ofstream ofs("out.txt"); while(p<=n){ if((c&((1<<27)-1))==0)ofs<>n; rep(i,385){ if(umekomi[i*2]<=n){ p=umekomi[i*2]; c=umekomi[i*2+1]; } } while(p