10 1 11 0 12 1 13 1 14 2 15 2 16 4 17 4 18 7 19 8 20 13 21 15 22 22 23 26 24 37 25 45 26 61 27 74 28 99 29 120 30 158 31 192 32 247 33 300 34 382 35 463 36 582 37 705 38 877 39 1059 40 1309 41 1575 42 1931 43 2319 44 2823 45 3381 46 4094 47 4886 48 5886 49 7007 50 8401 51 9971 52 11905 53 14090 54 16756 55 19781 56 23436 57 27594 58 32586 59 38268 60 45050 61 52780 62 61947 63 72406 64 84751 65 98835 66 115383 67 134267 68 156360 69 181568 70 210958 71 244467 72 283407 73 327791 74 379198 75 437758 76 505399 77 582383 78 671079 79 771952 80 887881 81 1019612 82 1170672 83 1342157 84 1538394 85 1760969 86 2015149 87 2303171 88 2631496 89 3003157 90 3426091 91 3904386 92 4447745 93 5061636 94 5757951 95 6543862 96 7433965 97 8437632 98 9572720 99 10851390 100 12295544 101 13920782 102 15753967 103 17815079 104 20136973 105 22745118 106 25679743 107 28973074 108 32674387 109 36824353 110 41483194 111 46702069 112 52554616 113 59104872 114 66442831 115 74648484 116 83831626 117 94091905 118 105563284 119 118369416 120 132673663 121 148629176 122 166434856 123 186279993 124 208406661 125 233048128 126 260498789 127 291045616 128 325046182 129 362852835 130 404899621 131 451618136 132 503534824 133 561177562 134 625184041 135 696198810 136 774993773 137 862354382 138 959214198 139 1066529003 140 1185426570 141 1317068198 142 1462815169 143 1624076153 144 1802492793 145 1999771571 146 2217890059 147 2458912702 148 2725219779 149 3019305083 150 3344030978 151 3702406220 152 4097869343 153 4534045935 154 5015063072 155 5545283887 156 6129657410 157 6773428367 158 7482525618 159 8263246367 160 9122687171 161 10068399897 162 11108871204 163 12253148012 164 13511369810 165 14894362983 166 16414231388 167 18083916728 168 19917855316 169 21931501959 170 24142059366 171 26567965051 172 29229701091 173 32149241166 174 35350951252 175 38860994681 176 42708332808 177 46924088229 178 51542656326 179 56601024021 180 62140006973 181 68203522164 182 74839963810 183 82101431335 184 90045259261 185 98733199203 186 108233123966 187 118618163554 188 129968602287 189 142370972496 190 155920166851 191 170718490616 192 186878017465 193 204519603258 194 223775512333 195 244788401119 196 267714246524 197 292721304607 198 319993380915 199 349728772511 200 382143919794 201 417472347053 202 455968741628 203 497907906019 204 543589320632 205 593336125319 206 647500223058 207 706461318104 208 770632627136 209 840459999566 210 916428317072 211 999060729255 212 1088925825501 213 1186637032072 214 1292860652915 215 1408315475383 216 1533781796038 217 1670101293088 218 1818187160280 219 1979024322025 220 2153680817107 221 2343308436945 222 2549155527195 223 2772568146964 224 3015004468585 225 3278036581058 226 3563366695296 227 3872829725501 228 4208411544021 229 4572252499643 230 4966667987788 231 5394153101462 232 5857405821147 233 6359333014162 234 6903076599612 235 7492021151135 236 8129823427333 237 8820421884810 238 9568070021226 239 10377348140277 240 11253201027071 241 12200952364935 242 13226347317899 243 14335570075496 244 15535291998756 245 16832692826806 246 18235515146003 247 19752089879206 248 21391397923481 249 23163100652250 250 25077609686853 251 27146123234523 252 29380705105593 253 31794327839877 254 34400962211647 255 37215628257451 256 40254496685282 257 43534949060348 258 47075692745523 259 50896831693458 260 55019996742882 261 59468428698183 262 64267126059201 263 69442942291104 264 75024753366581 265 81043571412357 266 87532734738029 267 94528040384202 268 102067959680664 269 110193792554819 270 118949912096261 271 128383943901975 272 138547043561420 273 149494104807159 274 161284074368363 275 173980193197493 276 187650353764730 277 202367379241596 278 218209428954064 279 235260321118225 280 253609992944114 281 273354873262843 282 294598404670939 283 317451473281260 284 342033001241653 285 368470441877000 286 396900452035862 287 427469461988395 288 460334438345773 289 495663539375116 290 533636980614961 291 574447787765891 292 618302778739794 293 665423427892616 294 716046980097774 295 770427441969732 296 828836845553145 297 891566384343807 298 958927846510941 299 1031254915864498 300 1108904797185643 301 1192259705007936 302 1281728706524430 303 1377749424158404 304 1480790124854040 305 1591351665809426 306 1709969862762620 307 1837217712175843 308 1973708075298809 309 2120096214551651 310 2277082834933602 311 2445416977258517 312 2625899463911813 313 2819386197216305 314 3026792062527189 315 3249094686393931 316 3487338856824615 317 3742640802962507 318 4016193200103314 319 4309270040657151 320 4623232300073824 321 4959533477983057 322 5319726010938340 323 5705467572738134 324 6118528330928243 325 6560798106802916 326 7034294584838797 327 7541171445871463 328 8083727652513668 329 8664416683435832 330 9285857033486571 331 9950842693375193 332 10662355020617585 333 11423574627387993 334 12237894798109919 335 13108934968794736 336 14040555889293430 337 15036874900677900 338 16102283064870630 339 17241462472805486 340 18459405592041741 341 19761434867604216 342 21153224569568225 343 22640822981391742 344 24230677064412915 345 25929657565508977 346 27745086854842697 347 29684767325953733 348 31757012807359450 349 33970680674667613 350 36335207285983707 351 38860644277861584 352 41557698529982262 353 44437773175004091 354 47513012660286891 355 50796349067202152 356 54301552907160078 357 58043285419433851 358 62037155816800539 359 66299780312918152 360 70848846620403861 361 75703180550859474 362 80882818665810638 363 86409083395666472 364 92304664853431817 365 98593705533995346 366 105301892423166392 367 112456552467767307 368 120086756249321000 369 128223425559960481 370 136899450063345501 371 146149808472626066 372 156011699792655070 373 166524679776817706 374 177730808535833279 375 189674804152275916 376 202404208655289221 377 215969560896890729 378 230424583131214378 379 245826375508730638 380 262235625765395147 381 279716827972622126 382 298338518139984730 383 318173520172824373 384 339299210525332928 385 361797794668687932 386 385756604302666818 387 411268408029189268 388 438431745045394534 389 467351274154283441 390 498138148325158166 391 530910406660839765 392 565793394727112116 393 602920204640281238 394 642432146642865439 395 684479243081533102 396 729220757348257925 397 776825748195076267 398 827473662874773705 399 881354958993091046 400 938671769480155117 401 999638600020427547 402 1064483074374495360 403 1133446716363097947 404 1206785785047661705 405 1284772151287633753 406 1367694233389886603 407 1455857979419096699 408 1549587915153130813 409 1649228244618889945 410 1755144023555710323 411 1867722392088324893 412 1987373888420020090 413 2114533829155067503 414 2249663779634667893 415 2393253099202892561 416 2545820586478891381 417 2707916208842650889 418 2880122943029130998 419 3063058710313637839 420 3257378435140381824 421 3463776209938125419 422 3682987597081329078 423 3915792049991693857 424 4163015486604876251 425 4425532996440946523 426 4704271716944790649 427 5000213859573444220 428 5314399923926954290 429 5647932079639340685 430 6001977757159518657 431 6377773426384135622 432 6776628607327480489 433 7199930091045709738 434 7649146418295879016 435 8125832593421407830 436 8631635084498025701 437 9168297086532687233 438 9737664102585698996 439 10341689818942896333 440 10982442333350320216 441 11662110711819030611 442 12383011937484642149 443 13147598226467743873 444 13958464779052984787 445 14818357940640456646 446 15730183846011818997 447 16697017520959382855 448 17722112520468160161 449 18808911077197479182 450 19961054845562626587 451 21182396214982348177 452 22477010284205634679 453 23849207470249051419 454 25303546851014845075 455 26844850215256938201 456 28478216926717138790 457 30209039576430160924 458 32043020538418958383 459 33986189403341152393 460 36044921414408715276 461 38225956880969134937 462 40536421703938861694 463 42983848989606445856 464 45576201896700478001 465 48321897694719025122 466 51229833190027283781 467 54309411499598238312 468 57570570341508116955 469 61023811824390227048 470 64680233918646235003 471 68551563594464231520 472 72650191824306442950 473 76989210438346664687 474 81582451046672522756 475 86444526020821311987 476 91590871766021512707 477 97037794281545827367 478 102802517259633916207 479 108903232726070262303 480 115359154493636247915 481 122190574438145437694 482 129418921890869555262 483 137066826164754759908 484 145158182532815374154 485 153718221684991694292 486 162773583008620052823 487 172352391729025231950 488 182484340284526283911 489 193200773984092492328 490 204534781353681170756 491 216521289232900557195 492 229197163062616178711 493 242601312440422311059 494 256774802422293079136 495 271760970664710258647 496 287605550926672370629 497 304356803045594909801 498 322065649951315006892 499 340785821854521977051 500 360574008222700714339 501 381490017705123063752 502 403596946673287434405 503 426961356566782787549 504 451653460769155262874 505 477747321235776506056 506 505321055661789845263 507 534457055448145400148 508 565242215323111522299 509 597768174917713260094 510 632131573228166732464 511 668434316309105940184 512 706783859213320902367 513 747293502572601067182 514 790082704925671088189 515 835277411244651160491 516 883010398864645029942 517 933421641331410649111 518 986658691479466821976 519 1042877084326526658940 520 1102240761214350596697 521 1164922515861047938491 522 1231104463883604627695 523 1300978536543869429828 524 1374747000417439845535 525 1452623003836919460007 526 1534831151962754826534 527 1621608111442453558697 528 1713203246679515217899 529 1809879288794449938732 530 1911913039483053593076 531 2019596110989422794422 532 2133235704599907581209 533 2253155429025532946749 534 2379696161298950820185 535 2513216951719977396404 536 2654095975716257232387 537 2802731534337823440337 538 2959543106515133041630 539 3124972455004118425504 540 3299484789435582177698 541 3483569988619347178043 542 3677743885835285245796 543 3882549619512878622967 544 4098559053375830234569 545 4326374268731466207538 546 4566629133358255593628 547 4819990949978835072986 548 5087162189184153637705 549 5368882310136329298311 550 5665929674366947446581 551 5979123556374433067042 552 6309326256830857224312 553 6657445322517270260416 554 7024435879338084918852 555 7411303082992449443656 556 7819104694244210822295 557 8248953783874970423381 558 8702021574908653997389 559 9179540427751108853410 560 9682806976540975201648 561 10213185422972032521517 562 10772110996657835222113 563 11361093588978909588500 564 11981721570330952841779 565 12635665798464001264470 566 13324683828758574089620 567 14050624334954960369086 568 14815431752196670217815 569 15621151151814433301642 570 16469933360822485090799 571 17364040336555967545073 572 18305850810636602738546 573 19297866213799180378021 574 20342716897095952201259 575 21443168662226328427464 576 22602129617964200988396 577 23822657376767073117133 578 25107966610131598142452 579 26461436978250285728395 580 27886621454276126663839 581 29387255060367217114282 582 30967264037724219725693 583 32630775469570963596908 584 34382127381376378569414 585 36225879339222730112120 586 38166823572899715186562 587 40209996646777459164994 588 42360691707533688341556 589 44624471334148140903477 590 47007181021969549226772 591 49514963328860567198330 592 52154272718212197119541 593 54931891129679886190445 594 57854944315699127842199 595 60930918977758268060229 596 64167680744058740745720 597 67573493025971273274450 598 71157036798825204857354 599 74927431348204611954433 600 78894256031560935342786 601 83067573100446939529593 602 87457951637853790260400 603 92076492660487884163317 604 96934855445577833385864 605 102045285137018550330266 606 107420641696028428845072 607 113074430256576697281222 608 119020832956863600787793 609 125274742313085643762204 610 131851796213444366677364 611 138768414605180380015724 612 146041837959888661149796 613 153690167597074482101291 614 161732407959182503429169 615 170188510925923049988375 616 179079422269846092958597 617 188427130349602783130386 618 198254717152372739617878 619 208586411791333970191646 620 219447646580065350211376 621 230865115800093288251348 622 242866837294849326689955 623 255482217017566206484067 624 268742116678809558662763 625 282678924633560795107389 626 297326630167128786144496 627 312720901333365461265406 628 328899166519298439898915 629 345900699904495237025214 630 363766711005477436171582 631 382540438489736735265012 632 402267248467371223563897 633 422994737462658028607023 634 444772840292911442967238 635 467653943076374264405979 636 491693001617601451651868 637 516947665413335911592565 638 543478407550386434152482 639 571348660761747219199210 640 600624959937636966865134 641 631377091383106149058163 642 663678249146367444296273 643 697605198737274978135811 644 733238448590102490436747 645 770662429620407191846994 646 809965683262870380126504 647 851241058373082310007830 648 894585917415897273039101 649 940102352359583258839043 650 987897410737391081475409 651 1038083332335379978774570 652 1090777797010681600889947 653 1146104184142312234028724 654 1204191844265150653753711 655 1265176383436456000936341 656 1329199960936205626534869 657 1396411600902244725265113 658 1466967518556796776017965 659 1541031461681690045018818 660 1618775068059137952738637 661 1700378239596965945801330 662 1786029533920880733226315 663 1875926574219851901421786 664 1970276478198918265057345 665 2069296306998813456653532 666 2173213535014930518332478 667 2282266541555043459143623 668 2396705125353583044650021 669 2516791042969207961885575 670 2642798572176446254197159 671 2775015101473424587032378 672 2913741746917823545871150 673 3059293997517017120555238 674 3212002390495029068977026 675 3372213217775642705826810 676 3540289265124733197226215 677 3716610585414816428813802 678 3901575307586143666006859 679 4095600482902187690743408 680 4299122970216892233237174 681 4512600361998571366353470 682 4736511952983698008090983 683 4971359753365780609916471 684 5217669548562392570784807 685 5475992007640313688120127 686 5746903842626863427603693 687 6031009020977872570408987 688 6328940033631916856654279 689 6641359221128863771518001 690 6968960160441883770753529 691 7312469115227210094685684 692 7672646552379891196428966 693 8050288727846323892426777 694 8446229344842187070217595 695 8861341287695123697907809 696 9296538434744316785312084 697 9752777553808861487170728 698 10231060283965782784618226 699 10732435207468257318116696 700 11258000015880973376568610 701 11808903774610234788060187 702 12386349290271601029031265 703 12991595585450593392464139 704 13625960485697490243784556 705 14290823323723242849830416 706 14987627766070959825022660 707 15717884767678003558475486 708 16483175660074830523440509 709 17285155379123325455580571 710 18125555838554031042976964 711 19006189455735882623832119 712 19928952836496317001400952 713 20895830626003131476238064 714 21908899533133548592639423 715 22970332535970611776959906 716 24082403276513328577536487 717 25247490652924842398885086 718 26468083618124004395052852 719 27746786193788990325225516 720 29086322709360295751537928 721 30489543275921537300770209 722 31959429505395801273032411 723 33499100485816824272018844 724 35111819024037502969746863 725 36800998167593084340591110 726 38570208018087040632446356 727 40423182848858913498739677 728 42363828540395336212141419 729 44396230347376539909651112 730 46524661012007989396015961 731 48753589238761398050459342 732 51087688546466608436874856 733 53531846514217950281092753 734 56091174438440670786271951 735 58771017419037044821262056 736 61576964893483746409539494 737 64514861638382711542588723 738 67590819258995359976982919 739 70811228187982490476037423 740 74182770215681602089491929 741 77712431575013250850013383 742 81407516605305927241938341 743 85275662020162305638833205 744 89324851805783210524634646 745 93563432777079145748240901 746 98000130820296110518787586 747 102644067851883262309227383 748 107504779524838647581908522 749 112592233714865212865121346 750 117916849820298838119071540 751 123489518910969772974572035 752 129321624762919081308686804 753 135425065817204206273983071 754 141812278102929315767498516 755 148496259166071473636791612 756 155490593047728047275042890 757 162809476356979891329580351 758 170467745485784461629234189 759 178480905015027678200892186 760 186865157363261663163687397 761 195637433731528475172937213 762 204815426400261500384081980 763 214417622436301367923660421 764 224463338870863750082730825 765 234972759411528885488707625 766 245966972754349110548887179 767 257468012564606764226384077 768 269498899198025617099530442 769 282083683236896366577110130 770 295247490919111743495196382 771 309016571541004679613578910 772 323418346918703698912137125 773 338481462995878930713136463 774 354235843689881804387465782 775 370712747071724615444729566 776 387944823979809887292515350 777 405966179171070933567042768 778 424812435118009994184889001 779 444520798564206651231317163 780 465130129956084796059216887 781 486681015873176318096375191 782 509215844584757590269783694 783 532778884865579399575233326 784 557416368209505525529240862 785 583176574585148115085342253 786 610109921884176293827664911 787 638269059218712267771450575 788 667708964231351284388178549 789 698487044587584029434957234 790 730663243828099297028559881 791 764300151765234170397339400 792 799463119616162180444779167 793 836220380072792837513715406 794 874643172517353730683783422 795 914805873600653008034365555 796 956786133409747098216591809 797 1000665017460463141555470431 798 1046527154760740978748065667 799 1094460892200240907374919773 800 1144558455533030971431497452 801 1196916117230469261347011581 802 1251634371493685408823760622 803 1308818116726256338001337716 804 1368576845780955715801967482 805 1431024844306611038102622451 806 1496281397535462853400700668 807 1564471005864619280210706828 808 1635723609600722692687604103 809 1710174823251275389320403119 810 1787966179762851876758387920 811 1869245385121980858108756710 812 1954166583752619406038222753 813 2042890635161024684205095222 814 2135585402298436143839398639 815 2232426052130301631472815731 816 2333595368921974947975658455 817 2439284080770689685130011634 818 2549691199936522642916313624 819 2665024377546623012309225553 820 2785500273271744399102031663 821 2911344940597504497316997934 822 3042794228339559584811467429 823 3180094199077244119104782952 824 3323501565209150495718756436 825 3473284143361625193677794797 826 3629721327912418506016102350 827 3793104584421540085305740449 828 3963737963795157300235199424 829 4141938638040692280455060403 830 4328037458507784612688199749 831 4522379537544814652190282944 832 4725324854540138439507944428 833 4937248887355144104661137967 834 5158543270198876588238062853 835 5389616479035106864154597865 836 5630894545658794421661564374 837 5882821801623450363834422485 838 6145861653250691569199377793 839 6420497389001543710920828754 840 6707233020542841197359074377 841 7006594158894350047972502340 842 7319128927100357306194969247 843 7645408910926085110062246766 844 7986030149142077892197681371 845 8341614165021014240751615546 846 8712809040739230799196781239 847 9100290536441617197594085006 848 9504763255801824497463163926 849 9926961859981580059938416793 850 10367652331972066732035755578 851 10827633293378096355064862821 852 11307737375791322110852217605 853 11808832648982906037963352740 854 12331824108238426955586068870 855 12877655223248901489991861118 856 13447309551071558760845290695 857 14041812415772569180259088370 858 14662232657471681983108441581 859 15309684453615359283531430194 860 15985329215421368369076402292 861 16690377562553148722577627334 862 17426091379207947046954833922 863 18193785954927489440339805080 864 18994832213575676161912411144 865 19830659034062736026307081224 866 20702755666541827565229401822 867 21612674247950015474150507090 868 22562032420923791182618921510 869 23552516060277115633810116073 870 24585882111400816225506207650 871 25663961545112794048205615976 872 26788662433672960368568047679 873 27961973152861281819259946535 874 29185965715216458537873761992 875 30462799239732157798258587013 876 31794723563522709057347359735 877 33184083001185690127332256376 878 34633320257820902824965416249 879 36144980501898166316785695942 880 37721715604416853895198378833 881 39366288551051815510893258547 882 41081578034250702787192930544 883 42870583232519704940331489333 884 44736428784426515726594295131 885 46682369965143222757123299712 886 48711798073666740937554248596 887 50828246039171891880807104362 888 53035394255292091980595339876 889 55337076651465564657928514184 890 57737287010851735501140777702 891 60240185544692903267341496610 892 62850105733392008188015724556 893 65571561444977399290836969858 894 68409254342052481571018393553 895 71368081588760182560888701792 896 74453143869752847865264367166 897 77669753733624725468256162327 898 81023444273761187972215494175 899 84519978160062591202602948232 900 88165357035536807262813162186 901 91965831292298335193316986065 902 95927910242090231212718842027 903 100058372697032223342257745368 904 104364277976922196556166327924 905 108852977360051999457807750845 906 113532125995171362957423970350 907 118409695292917773330268853322 908 123493985815755806662171054504 909 128793640686207696187216427232 910 134317659533939492772347443764 911 140075413003063883258104260596 912 146076657841864657265488077730 913 152331552598007509524988659113 914 158850673943211878668398396235 915 165645033652286113156578006724 916 172726096262409471032253766550 917 180105797439545220169432361059 918 187796563079927028731832598791 919 195811329175640446788112905016 920 204163562474461835197351841816 921 212867281965281675914051135152 922 221937081221668762103827080489 923 231388151637387894150035445554 924 241236306589009143771483301794 925 251498006562101511160650742369 926 262190385278932493312000140205 927 273331276867056105065701802052 928 284939244109711791627602416631 929 297033607820532161950341158482 930 309634477386717124223431500658 931 322762782526530793769091697320 932 336440306308766149849912454963 933 350689719483654007954014923003 934 365534616176620332075737399478 935 380999550998270526920557687681 936 397110077626056306962377136725 937 413892788915209380175551604200 938 431375358598764093590431616534 939 449586584638785688178217210086 940 468556434293331991676511662587 941 488316090966149467932391515932 942 508898002908702244510395991802 943 530335933846798113102899728258 944 552665015606873973039107083332 945 575921802819875571950793288942 946 600144329783680971260948196332 947 625372169568112399100922964043 948 651646495449828304724844099423 949 679010144767722549658348695548 950 707507685292955120749584189483 951 737185484211332076482541445258 952 768091779819519239682128072128 953 800276756040445378894263806436 954 833792619867307259400152656125 955 868693681849759256401840551672 956 905036439740238721427150147691 957 942879665422870457904214212633 958 982284495252097694911175195606 959 1023314523933025446603108516955 960 1066035902080527161191561481201 961 1110517437599376711624929240511 962 1156830701033121133838467284137 963 1205050135035021604405862782406 964 1255253168120261240529800240148 965 1307520332864661734313933347849 966 1361935388721471258848232740917 967 1418585449634293534790850725406 968 1477561116631031662393961424169 969 1538956615590726917815429156946 970 1602869940382496208588957057911 971 1669403001583315361771807745379 972 1738661780989277902567840903532 973 1810756492143079901028945804292 974 1885801747108965064844070896286 975 1963916729735106195041021507916 976 2045225375652529099749421876194 977 2129856559269094840339958580535 978 2217944288026881166307161100447 979 2309627904201431917737382090117 980 2405052294531915396573094424421 981 2504368107982132813665341913837 982 2607731981943693493259637347642 983 2715306777204403856568115142606 984 2827261822017156404150151877584 985 2943773165617227846569480204386 986 3065023841549063088839573101595 987 3191204141177204268691355929649 988 3322511897770189486912010263069 989 3459152781560859859501917304384 990 3601340606201751505411637322735 991 3749297647049971823423494200876 992 3903254971732350119588068740709 993 4063452783458567093292834049752 994 4230140777567597216100893390536 995 4403578511810993272826244380002 996 4584035790895503120250726695609 997 4771793065827080393822337837726 998 4967141848618742189296213101972 999 5170385142945777558924491933889 1000 5381837891353739024066597803129