1 0 2 1 3 0 4 2 5 1 6 3 7 3 8 6 9 5 10 11 11 11 12 17 13 20 14 30 15 33 16 49 17 56 18 77 19 92 20 122 21 143 22 190 23 225 24 287 25 344 26 435 27 516 28 648 29 770 30 951 31 1134 32 1388 33 1646 34 2007 35 2376 36 2868 37 3395 38 4078 39 4807 40 5749 41 6764 42 8042 43 9449 44 11187 45 13101 46 15463 47 18070 48 21236 49 24772 50 29021 51 33764 52 39445 53 45798 54 53337 55 61812 56 71797 57 83019 58 96209 59 111034 60 128346 61 147863 62 170546 63 196097 64 225721 65 259085 66 297605 67 341033 68 390996 69 447282 70 511909 71 584673 72 667953 73 761748 74 868819 75 989298 76 1126587 77 1280961 78 1456461 79 1653749 80 1877565 81 2128951 82 2413708 83 2733283 84 3094591 85 3499880 86 3957331 87 4470004 88 5047878 89 5694986 90 6423264 91 7238275 92 8154214 93 9178357 94 10327958 95 11612305 96 13052093 97 14659528 98 16459322 99 18466998 100 20712516 101 23215409 102 26011642 103 29126132 104 32601918 105 36470225 106 40783112 107 45579345 108 50921445 109 56858010 110 63463938 111 70799388 112 78954723 113 88004026 114 98055755 115 109201558 116 121571373 117 135277694 118 150476926 119 167306525 120 185954023 121 206587931 122 229432736 123 254693771 124 282640589 125 313522638 126 347662638 127 385364045 128 427012696 129 472976249 130 523716866 131 579678825 132 641414425 133 709460960 134 784477649 135 867112125 136 958152087 137 1058376639 138 1168725231 139 1290135201 140 1423725748 141 1570621861 142 1732157561 143 1909680662 144 2104778775 145 2319066450 146 2554431195 147 2812803109 148 3096426547 149 3407605543 150 3749005205 151 4123374786 152 4533876042 153 4983784111 154 5476849469 155 6016968639 156 6608585290 157 7256332875 158 7965471703 159 8741503662 160 9590653878 161 10519448138 162 11535245698 163 12645782001 164 13859749761 165 15186307198 166 16635717808 167 18218812998 168 19947699461 169 21835179368 170 23895522201 171 26143842992 172 28596952057 173 31272678475 174 34190808635 175 37372358905 176 40840600900 177 44620284109 178 48738764436 179 53225162119 180 58111608183 181 63432342843 182 69225078200 183 75530038774 184 82391462048 185 89856564628 186 97977199144 187 106808752889 188 116411961963 189 126851745316 190 138199203164 191 150530368441 192 163928414354 193 178482332886 194 194289354807 195 211453560389 196 230088547680 197 250315956332 198 272268416431 199 296087999086 200 321929454805 201 349958599804 202 380355889647 203 413314722507 204 449045392095 205 487773327583 206 529743441859 207 575218322905 208 624483038806 209 677843263900 210 735630598885 211 798200660894 212 865938947244 213 939258913815 214 1018608463153 215 1104467999870 216 1197357623716 217 1297835205009 218 1406504328214 219 1524012426442 220 1651059585240 221 1788396735631 222 1936835427232 223 2097246144180 224 2270569120718 225 2457812841621 226 2660066047950 227 2878496440020 228 3114364025766 229 3369020122222 230 3643922157645 231 3940633067671 232 4260837754684 233 4606342927997 234 4979095430878 235 5381182668006 236 5814852970537 237 6282516758566 238 6786769223611 239 7330392325232 240 7916380086897 241 8547941640293 242 9228529387685 243 9961843319450 244 10751862432637 245 11602850498434 246 12519391151165 247 13506395422543 248 14569140879131 249 15713281263914 250 16944890224365 251 18270473357000 252 19697017112071 253 21232003710466 254 22883465779542 255 24660004652678 256 26570851499255 257 28625889481147 258 30835722203727 259 33211700421375 260 35765998623875 261 38511647050451 262 41462617482800 263 44633861308962 264 48041405697350 265 51702398726896 266 55635217125928 267 59859519591319 268 64396367607268 269 69268288088254 270 74499408941334 271 80115532520374 272 86144287651392 273 92615215548964 274 99559940443623 275 107012269671779 276 115008385270922 277 123586960410365 278 132789374435737 279 142659848054649 280 153245684861345 281 164597427827804 282 176769130664415 283 189818538763686 284 203807393972938 285 218801643503687 286 234871782404976 287 252093094202251 288 270546035840266 289 290316514603401 290 311496320655853 291 334183445333611 292 358482567358270 293 384505418011740 294 412371327785563 295 442207644999040 296 474150350225224 297 508344535695864 298 544945096100663 299 584117276793138 300 626037450551972 301 670893744011242 302 718886910852387 303 770231047013299 304 825154572473351 305 883901046827021 306 946730273232026 307 1013919227837032 308 1085763300794120 309 1162577354653704 310 1244697119618081 311 1332480397567239 312 1426308630741763 313 1526588270649312 314 1633752541318552 315 1748262994652948 316 1870611492496475 317 2001321972290619 318 2140952675029509 319 2290098148604456 320 2449391751583287 321 2619507924918190 322 2801165005692413 323 2995127801204965 324 3202210750844159 325 3423280841389897 326 3659261159280961 327 3911134190630817 328 4179945811919513 329 4466809023034261 330 4772908430050276 331 5099504466229871 332 5447938426445076 333 5819637237628255 334 6216119112268812 335 6638998936696264 336 7089994618998418 337 7570933172615236 338 8083757842375279 339 8630534970089496 340 9213461993225503 341 9834875188976496 342 10497258651141757 343 11203253021657266 344 11955665563062468 345 12757479999368735 346 13611867816334388 347 14522199347368948 348 15492056449263822 349 16525244986042943 350 17625809044378588 351 18798044986286775 352 20046517388861703 353 21376074856138656 354 22791867889216282 355 24299366671288871 356 25904381097455178 357 27613080771950482 358 29432017454945903 359 31368147538190997 360 33428857195870122 361 35621987637430319 362 37955863281926295 363 40439320121545090 364 43081737277348171 365 45893068844886821 366 48883879230427334 367 52065378894802301 368 55449463914202593 369 59048756086498669 370 62876647213455253 371 66947344086376888 372 71275918043500096 373 75878355413261942 374 80771612962931871 375 85973674444216003 376 91503612621573019 377 97381652637723297 378 103629241388484294 379 110269118510029529 380 117325393953172114 381 124823627485732687 382 132790915418307528 383 141255979615692274 384 150249264434015210 385 159803036350607861 386 169951492290962585 387 180730871112263933 388 192179574634246834 389 204338292350103306 390 217250136623301045 391 230960782157515527 392 245518616984460584 393 260974898397124033 394 277383921538922323 395 294803193694742724 396 313293622494479706 397 332919710672142236 398 353749766120266934 399 375856119463711048 400 399315358454251031 401 424208570966333781 402 450621606498313249 403 478645347491747894 404 508376001011441157 405 539915401612849886 406 573371336617514479 407 608857884109497937 408 646495775601018068 409 686412773139706280 410 728744073576555338 411 773632729206274464 412 821230098318292652 413 871696314278646116 414 925200787559899681 415 981922728718159911 416 1042051707666354994 417 1105788236599582824 418 1173344392912752898 419 1244944468789376756 420 1320825664864982694 421 1401238813934681367 422 1486449153236830355 423 1576737130549448270 424 1672399263832090294 425 1773749038880573460 426 1881117866015562764 427 1994856079468585018 428 2115334001855072913 429 2242943056569705412 430 2378096951951026889 431 2521232919183944291 432 2672813029350926563 433 2833325570697803952 434 3003286513187917470 435 3183241040483574407 436 3373765178200840579 437 3575467497610305572 438 3788990925532072859 439 4015014638595169189 440 4254256074634467662 441 4507473038370417274 442 4775465936304596255 443 5059080116912930960 444 5359208353388661988 445 5676793443919153150 446 6012830969219875327 447 6368372181193808806 448 6744527065078237497 449 7142467547796076780 450 7563430897707987931 451 8008723287301985976 452 8479723567040500654 453 8977887220710888577 454 9504750553731132474 455 10061935083538040528 456 10651152186982861665 457 11274207972622810420 458 11933008436543115055 459 12629564868362059914 460 13365999570022810574 461 14144551852773135994 462 14967584379204988195 463 15837589814499162252 464 16757197858311351880 465 17729182620211864205 466 18756470415004289245 467 19842147939607660290 468 20989470913088128493 469 22201873140316608975 470 23482976086471188211 471 24836598921705897127 472 26266769129244808982 473 27777733635104716866 474 29373970559209415144 475 31060201545036650259 476 32841404774533523533 477 34722828624476321836 478 36710006078496211770 479 38808769850064576900 480 41025268338726085025 481 43365982374100246353 482 45837742878598335643 483 48447749402763387217 484 51203589673486510723 485 54113260108543754838 486 57185187447743339114 487 60428251453849121859 488 63851808844356846861 489 67465718407258761081 490 71280367473479866868 491 75306699699335356647 492 79556244344219943201 493 84041146997384264735 494 88774201952489280165 495 93768886184670245264 496 99039395143322450035 497 104600680316592864216 498 110468488796475760615 499 116659404802188904846 500 123190893407627270315 501 130081346432802636519 502 137350130763289902067 503 145017639060378882252 504 153105343145653633638 505 161635850026131902269 506 170632960864935700220 507 180121732867829111579 508 190128544413533484447 509 200681163403167712476 510 211808819181541934394 511 223542278011585265867 512 235913922481432898196 513 248957834832467809757 514 262709884616799891451 515 277207820680639720104 516 292491367913402891752 517 308602328768461529542 518 325584690029266585950 519 343484734837719634024 520 362351160495172155312 521 382235202065498134796 522 403190762330333224546 523 425274548140297684718 524 448546213755263200340 525 473068511233919277240 526 498907448512214908344 527 526132455249589700164 528 554816557133004008437 529 585036558738823883416 530 616873235697181473194 531 650411536282829633897 532 685740793236280783683 533 722954945966253309103 534 762152774001409034532 535 803438141872798937205 536 846920256364566892155 537 892713936348546981400 538 940939896215732526810 539 991725043158606491593 540 1045202789399190926410 541 1101513379659752559692 542 1160804235059819159193 543 1223230313784546412266 544 1288954489804433250113 545 1358147950045114679652 546 1430990611391866757165 547 1507671557987430803799 548 1588389500321341655692 549 1673353256636158959050 550 1762782258272058944826 551 1856907079549483172892 552 1955969993945246498515 553 2060225557244393390802 554 2169941219568642450700 555 2285397967055533878214 556 2406890995247091498521 557 2534730415063974624527 558 2669241993595647154111 559 2810767930695469540583 560 2959667673797782538727 561 3116318772071100822282 562 3281117772527193583049 563 3454481159338744193501 564 3636846339205784837307 565 3828672674176886579752 566 4030442565004851253327 567 4242662586612457060451 568 4465864679008413651077 569 4700607395416374841275 570 4947477211240405941195 571 5207089895836542087411 572 5480091951021768955912 573 5767162118518370868638 574 6069012960599830211263 575 6386392516387968733200 576 6720086038431809349697 577 7070917812295334565322 578 7439753064180788875617 579 7827499959620550822549 580 8235111698695130729257 581 8663588711147067377131 582 9113980957317160080334 583 9587390338643453759350 584 10084973224159435543166 585 10607943097139793317855 586 11157573328885049527375 587 11735200084241980378857 588 12342225366454962024454 589 12980120206438237652451 590 13650428004721172246117 591 14354768031698480685707 592 15094839095152270531900 593 15872423381273165796137 594 16689390478925284700881 595 17547701594035966777874 596 18449413964701464976624 597 19396685484607136829334 598 20391779546274421205478 599 21437070112520516095606 600 22535047028645548131135 601 23688321584596831284815 602 24899632340715882753104 603 26171851227265084341389 604 27507989932526778208120 605 28911206590710064769987 606 30384812785750182074122 607 31932280883373693596075 608 33557251708920405324198 609 35263542584542203573259 610 37055155744799848461694 611 38936287145643621251788 612 40911335687464235713291 613 42984912868695338843539 614 45161852892466254582004 615 47447223244423593117412 616 49846335766192500449885 617 52364758244387982904592 618 55008326541793424054595 619 57783157292577234372098 620 60695661190500295535173 621 63752556894129985299416 622 66960885580554902439500 623 70328026173961653598337 624 73861711283333577312094 625 77570043878197361411071 626 81461514739686791366848 627 85545020718653334151522 628 89829883841367217919998 629 94325871297602817974217 630 99043216355215048896811 631 103992640239348601027005 632 109185375024263234864859 633 114633187579574809307047 634 120348404623112769404693 635 126343938926188803524479 636 132633316728066076081087 637 139230706409786301509447 638 146150948489135878799690 639 153409586991671688658611 640 161022902265018006662841 641 169007945296554564172884 642 177382573607614487328875 643 186165488789986656440664 644 195376275764266593804541 645 205035443832042701186398 646 215164469608450644053090 647 225785841913838220233360 648 236923108718674926500066 649 248600926227817381419919 650 260845110206531644237058 651 273682689642420458008628 652 287141962854646573809882 653 301252556153363565102686 654 316045485170521887638344 655 331553218974515716803634 656 347809747100468926957025 657 364850649619040751983919 658 382713170387108159198820 659 401436293614556439628492 660 421060823903102528788811 661 441629469903751795888540 662 463186931762475585454059 663 485779992514187551219717 664 509457613609458783173620 665 534271034748731413570788 666 560273878224616505125121 667 587522257963027285530847 668 616074893481283044536465 669 645993228971350719047043 670 677341557745433622134957 671 710187152271038215030854 672 744600400053458781017091 673 780654945613457479843765 674 818427838840607696876388 675 857999689992554222928407 676 899454831645138224260934 677 942881487888103871736474 678 988371951097934518784078 679 1036022766609158148933830 680 1085934925644570338018617 681 1138214066854684219235809 682 1192970686858253322382127 683 1250320360165695142636382 684 1310383968911370197010712 685 1373287942810831275430575 686 1439164509806048116801750 687 1508151957852016617279549 688 1580394908348000725133615 689 1656044601707375576628551 690 1735259195613027948428854 691 1818204076496387524912809 692 1905052184834511550266215 693 1995984354851251513623580 694 2091189669268468968816346 695 2190865829745462921458719 696 2295219543708545326156981 697 2404466928265596911750811 698 2518833931968308099352736 699 2638556775178531070771326 700 2763882409867421257780409 701 2895068999670730681349305 702 3032386421100551346426602 703 3176116786809605001788814 704 3326554991886119553454725 705 3484009284154413600982659 706 3648801859543610470183947 707 3821269483585452360033158 708 4001764140195216691390015 709 4190653708889957145767298 710 4388322671697456622978170 711 4595172851011396965937105 712 4811624179753978901968271 713 5038115505211487380329473 714 5275105428021054995215952 715 5523073177793552498442176 716 5782519526977819611206478 717 6053967744580839914659132 718 6337964591486808446518172 719 6635081359130472329056902 720 6945914953417106790590074 721 7271089025797319203602497 722 7611255153551110654623252 723 7967094071355247910845880 724 8339316956364153328086263 725 8728666769058366537414202 726 9135919652281419904628342 727 9561886390914508305234281 728 10007413934816522703272108 729 10473386987690764208752028 730 10960729664730069016552353 731 11470407221931592519983573 732 12003427860176028812733036 733 12560844607211943211165397 734 13143757280903491749485381 735 13753314537152759057046111 736 14390716006140635926379656 737 15057214520590902722125680 738 15754118440011074656353039 739 16482794074932893627081562 740 17244668215441628868190725 741 18041230768362133212157385 742 18874037507754543565021783 743 19744712943461702206034975 744 20654953312755359068359599 745 21606529700228837459694328 746 22601291291410350460946646 747 23641168765684338356000310 748 24728177834457814217591604 749 25864422930635671873480977 750 27052101055843355536693204 751 28293505791977370853682968 752 29591031484065234653959187 753 30947177601575104903841008 754 32364553285745105853797299 755 33845882090679145075898715 756 35394006926416588261599430 757 37011895212379785783097417 758 38702644250097109928604582 759 40469486824317498062074018 760 42315797042161732011634941 761 44245096420197747388713226 762 46261060229894740728348841 763 48367524112178823404135081 764 50568490972421554465687388 765 52868138167488966769971727 766 55270824997131481071458455 767 57781100512322269184663052 768 60403711653851935220426045 769 63143611734848235422084985 770 66005969281640974734250450 771 68996177247789798898747552 772 72119862616898983350463026 773 75382896410280927109049148 774 78791404116395564454225714 775 82351776559474113177276399 776 86070681225664677205128981 777 89955074065565905665776408 778 94012211793012417696473769 779 98249664700556064359880473 780 102675330013158204848307385 781 107297445802244761980589006 782 112124605483426111066032986 783 117165772921881603351379708 784 122430298170644009306692138 785 127927933867783411841705195 786 133668852319817239667676615 787 139663663299509651692854802 788 145923432587649293955641304 789 152459701289309510101609441 790 159284505956627055745719596 791 166410399551135739210942103 792 173850473280337632578614481 793 181618379344287509858330759 794 189728354629735352882490394 795 198195245390565356345876476 796 207034532955171386836231851 797 216262360502711600354186879 798 225895560952228892613716599 799 235951686010045043480945537 800 246449036423033710798821457 801 257406693486927096539757154 802 268844551861173437122575678 803 280783353743551471295117176 804 293244724460288023023514164 805 306251209529264902668423714 806 319826313256632552259385073 807 333994538929151680224596725 808 348781430667521215566093639 809 364213617008132192268011606 810 380318856283845878207624704 811 397126083876768014021124855 812 414665461419388309193277981 813 432968428023036175172897585 814 452067753616257793237027496 815 471997594478527017871440649 816 492793551058633240083226693 817 514492728170140979719360671 818 537133797660544275984829714 819 560757063654055007638751144 820 585404530472513041234766703 821 611119973342508364651727427 822 637949012001699145805283755 823 665939187321221622776581000 824 695140041066352951549690088 825 725603198921835205140271545 826 757382456913933816129805144 827 790533871365913325410292327 828 825115852529708907475871019 829 861189262041573786907351279 830 898817514356041743305159319 831 938066682317969544115108106 832 979005607039482185030184039 833 1021706012254527895422560970 834 1066242623331345073021924564 835 1112693291129522975437510197 836 1161139120896511487795894924 837 1211664606405350625577600917 838 1264357769544186461842836667 839 1319310305575634417757369741 840 1376617734293517070082433660 841 1436379557312623412101831417 842 1498699421737324173920732801 843 1563685290463673418216413979 844 1631449619380590925202332330 845 1702109541745245538295663140 846 1775787060019559961686174365 847 1852609245465071659191783727 848 1932708445806084750516202631 849 2016222501282213491848886151 850 2103294969425086864127135166 851 2194075358906068948304223518 852 2288719372816561403217607675 853 2387389161755532196208203352 854 2490253587114748695827788898 855 2597488494966342670541298254 856 2709277000974376684454977605 857 2825809786767387448642092832 858 2947285408227223808882858253 859 3073910616166051367323684641 860 3205900689883137199870266034 861 3343479784110929423333075874 862 3486881289881193850777260131 863 3636348209861324583407324216 864 3792133548733813672630263163 865 3954500719212787456145299947 866 4123723964316129713787614238 867 4300088796534325512506690655 868 4483892454563649196620748031 869 4675444378295757832674428294 870 4875066702784260899796402395 871 5083094771935242082654831580 872 5299877672699392026355358874 873 5525778790571937284448370463 874 5761176387239572429801854850 875 6006464201244415867164098804 876 6262052072570548065008740911 877 6528366592091970278277678844 878 6805851776859067535007075623 879 7094969772236597071587734439 880 7396201581947382093010620661 881 7710047827114693146663193477 882 8037029535440592040188284343 883 8377688961699403369552018694 884 8732590440773142876648105708 885 9102321274500949437942268662 886 9487492653665858556342964996 887 9888740616491058206660250492 888 10306727045072960489540986077 889 10742140701231088472307777420 890 11195698303314166937689988496 891 11668145645558633284210407060 892 12160258761659688232745484713 893 12672845134276316398743203373 894 13206744952260465406586579310 895 13762832417466711120190271165 896 14342017103072717043815750088 897 14945245365412135130639979535 898 15573501811401191654738282184 899 16227810823717141141180991329 900 16909238145972407271880840021 901 17618892530211199224010249721 902 18357927449147522505216767567 903 19127542875652965596522867162 904 19928987132101758144529164102 905 20763558812277048717265798408 906 21632608778648974043711840390 907 22537542237939068678198851695 908 23479820898000262204919243529 909 24460965209153787813251783802 910 25482556693247705347686770468 911 26546240363822536425475287152 912 27653727240902221600790875218 913 28806796964058786231218541372 914 30007300507541847651377140317 915 31257163001404369345809452466 916 32558386662709599785479245717 917 33913053841055270723989838224 918 35323330182816256087713726121 919 36791467918669718765080845256 920 38319809279144361554534189344 921 39910790043110800376571663365 922 41566943224321061988025746180 923 43290902901294138689725090121 924 45085408196049913473022872135 925 46953307407397251409847930458 926 48897562304702906564556953639 927 50921252588287028107814084211 928 53027580522828530485737982457 929 55219875750399560622629093562 930 57501600290003644539863703660 931 59876353730746167048852199047 932 62347878626040387836208133609 933 64920066096525735346707595687 934 67596961649670299989651254549 935 70382771224323917789095796877 936 73281867468805581782254758505 937 76298796261425892696668491008 938 79438283482686421265428993454 939 82705242048739022933833980975 940 86104779216054890974621487772 941 89642204167620310927152035515 942 93323035891370308855363730001 943 97153011361966519563871996316 944 101138094037449354118923739991 945 105284482682719728379726802741 946 109598620532261079955332586805 947 114087204804969878109461268602 948 118757196584452358702877876417 949 123615831078637399424971791930 950 128670628273081561335637655396 951 133929403992871800607772672482 952 139400281388596754127103178105 953 145091702862427053919295398733 954 151012442450952717800647992466 955 157171618682038271010974911937 956 163578707923609154373939997579 957 170243558242941839252848768478 958 177176403795731621773724085961 959 184387879764920626570551144311 960 191889037870022340825143227415 961 199691362468440937251057953851 962 207806787271093521671974914001 963 216247712695462715411015917112 964 225027023880077074458511653241 965 234158109385297704090558437498 966 243654880606224162715421720800 967 253531791924479742693913141594 968 263803861626640344714844839379 969 274486693618089180723037379025 970 285596499962158158231260812071 971 297150124275511084671715698749 972 309165066011882402278605637999 973 321659505667461341534122934410 974 334652330942455768127042891829 975 348163163894634100757529971678 976 362212389121980164654613983341 977 376821183012954343990486880339 978 392011544104289724993910582603 979 407806324587711756255707661063 980 424229263008511350175989682102 981 441305018200469964056247513007 982 459059204503290415493811443356 983 477518428310372563479560471412 984 496710325996550330792547409186 985 516663603277217241890720090431 986 537408076052176031255910705582 987 558974712789493075960105690545 988 581395678506687373964462142560 989 604704380408673329603060995032 990 628935515244076400557995182902 991 654125118443785092439840320763 992 680310615107964379588384002522 993 707530872910166265573678524736 994 735826256989708352317608237323 995 765238686906080250191081451467 996 795811695731858988003445584839 997 827590491363394871511831741780 998 860622020131450249545339200631 999 894955032796959194776366854061 1000 930640153020211282063039602444