1 0 2 0 3 1 4 0 5 0 6 2 7 0 8 0 9 2 10 0 11 1 12 3 13 0 14 2 15 3 16 0 17 3 18 4 19 1 20 4 21 4 22 3 23 5 24 5 25 5 26 6 27 6 28 8 29 7 30 9 31 10 32 8 33 13 34 13 35 10 36 18 37 15 38 14 39 23 40 18 41 20 42 29 43 21 44 29 45 34 46 27 47 38 48 40 49 36 50 49 51 46 52 49 53 59 54 56 55 65 56 71 57 70 58 83 59 82 60 91 61 102 62 98 63 116 64 122 65 119 66 148 67 143 68 150 69 180 70 169 71 189 72 217 73 202 74 237 75 253 76 249 77 291 78 297 79 308 80 350 81 349 82 383 83 412 84 420 85 467 86 482 87 509 88 564 89 564 90 622 91 664 92 670 93 752 94 778 95 803 96 901 97 905 98 971 99 1062 100 1065 101 1167 102 1240 103 1261 104 1395 105 1439 106 1507 107 1642 108 1679 109 1798 110 1919 111 1969 112 2137 113 2222 114 2330 115 2512 116 2581 117 2756 118 2929 119 3006 120 3258 121 3389 122 3527 123 3816 124 3920 125 4145 126 4442 127 4542 128 4871 129 5127 130 5293 131 5690 132 5913 133 6181 134 6607 135 6816 136 7227 137 7618 138 7895 139 8411 140 8761 141 9162 142 9746 143 10068 144 10652 145 11216 146 11605 147 12349 148 12872 149 13403 150 14264 151 14745 152 15511 153 16384 154 16928 155 17916 156 18758 157 19462 158 20641 159 21430 160 22421 161 23661 162 24511 163 25804 164 27040 165 28068 166 29639 167 30820 168 32202 169 33907 170 35145 171 36927 172 38669 173 40105 174 42292 175 43986 176 45843 177 48270 178 50022 179 52396 180 54943 181 56908 182 59836 183 62366 184 64832 185 68147 186 70753 187 73869 188 77414 189 80263 190 84128 191 87716 192 91154 193 95599 194 99293 195 103548 196 108396 197 112366 198 117604 199 122597 200 127262 201 133340 202 138504 203 144172 204 150889 205 156383 206 163328 207 170358 208 176668 209 184781 210 192093 211 199630 212 208711 213 216441 214 225598 215 235241 216 243944 217 254686 218 264793 219 274992 220 287126 221 297788 222 310040 223 323088 224 334919 225 349281 226 363062 227 376713 228 393045 229 407583 230 423794 231 441539 232 457504 233 476481 234 495371 235 513542 236 535210 237 555178 238 576532 239 600288 240 622037 241 646958 242 672427 243 696879 244 725430 245 752433 246 780819 247 812353 248 841614 249 874569 250 908619 251 941195 252 978958 253 1015197 254 1052630 255 1094564 256 1133713 257 1176934 258 1222471 259 1265724 260 1315242 261 1363895 262 1413125 263 1468349 264 1520808 265 1577327 266 1637624 267 1695206 268 1759858 269 1824548 270 1889516 271 1961842 272 2031557 273 2105659 274 2184979 275 2261148 276 2345700 277 2431140 278 2516428 279 2611168 280 2703271 281 2799972 282 2904251 283 3004531 284 3114518 285 3227254 286 3338835 287 3462188 288 3583808 289 3709594 290 3845745 291 3977828 292 4120431 293 4268121 294 4414259 295 4574210 296 4733725 297 4897550 298 5074506 299 5247455 300 5432446 301 5624984 302 5815473 303 6022820 304 6231084 305 6443554 306 6673248 307 6898843 308 7137863 309 7388411 310 7635965 311 7903561 312 8174950 313 8449839 314 8746568 315 9040378 316 9348430 317 9672800 318 9994219 319 10338584 320 10690474 321 11045903 322 11427902 323 11808833 324 12205640 325 12623965 326 13039692 327 13482406 328 13936867 329 14394959 330 14886016 331 15378073 332 15887649 333 16426101 334 16962117 335 17529479 336 18115198 337 18704009 338 19333024 339 19967412 340 20620231 341 21310632 342 22000683 343 22725938 344 23477790 345 24233761 346 25037268 347 25851981 348 26687454 349 27569940 350 28455195 351 29381238 352 30343248 353 31310857 354 32335713 355 33378730 356 34445043 357 35570964 358 36703437 359 37882653 360 39110942 361 40346417 362 41649925 363 42982337 364 44340285 365 45772395 366 47218261 367 48716669 368 50279953 369 51854736 370 53508843 371 55205538 372 56932327 373 58749297 374 60589803 375 62491021 376 64475231 377 66477176 378 68572898 379 70727473 380 72918015 381 75219106 382 77555757 383 79962607 384 82476088 385 85014899 386 87663951 387 90394301 388 93167116 389 96074113 390 99034747 391 102075424 392 105250940 393 108464761 394 111806349 395 115256970 396 118761137 397 122425512 398 126166833 399 130002440 400 134005057 401 138063297 402 142271908 403 146622325 404 151040751 405 155652071 406 160368803 407 165196900 408 170232707 409 175345891 410 180635513 411 186109628 412 191669521 413 197460030 414 203394781 415 209460672 416 215782179 417 222212449 418 228848352 419 235720425 420 242704576 421 249961867 422 257411946 423 265020623 424 272939970 425 281008711 426 289320440 427 297929234 428 306684381 429 315765174 430 325097525 431 334622974 432 344526986 433 354630722 434 365022048 435 375786913 436 386740772 437 398081881 438 409750558 439 421653807 440 434015642 441 446644847 442 459613262 443 473046920 444 486728329 445 500867350 446 515427229 447 530278061 448 545679651 449 561433685 450 577593361 451 594325833 452 611381027 453 628981017 454 647113703 455 665608221 456 684766267 457 704381149 458 724482282 459 745288767 460 766511165 461 788381452 462 810924807 463 833917422 464 857706375 465 882086376 466 907049108 467 932874836 468 959238785 469 986371359 470 1014346813 471 1042886229 472 1072376713 473 1102624046 474 1133577160 475 1165578524 476 1198271594 477 1231882287 478 1266538451 479 1301902757 480 1338406018 481 1375867425 482 1414186067 483 1453778049 484 1494250745 485 1535820112 486 1578683945 487 1622433604 488 1667545147 489 1713866735 490 1761229221 491 1810132584 492 1860157213 493 1911490995 494 1964418247 495 2018459275 496 2074123882 497 2131305546 498 2189760711 499 2250071295 500 2311800482 501 2375101796 502 2440351578 503 2506998437 504 2575586797 505 2646061941 506 2718097075 507 2792367824 508 2868420020 509 2946362181 510 3026684113 511 3108751299 512 3193138799 513 3279867554 514 3368506064 515 3459831554 516 3553390442 517 3649221507 518 3747947149 519 3848855340 520 3952533127 521 4059100663 522 4168015667 523 4280150827 524 4395071382 525 4512735221 526 4633904248 527 4757794442 528 4884999232 529 5015750545 530 5149387352 531 5286885862 532 5427837987 533 5572105957 534 5720614632 535 5872501435 536 6028356158 537 6188554685 538 6352294555 539 6520659857 540 6693298316 541 6869943780 542 7051706112 543 7237659517 544 7428360061 545 7624360544 546 7824714807 547 8030599040 548 8241748343 549 8457754219 550 8679915007 551 8907258417 552 9140294566 553 9379770328 554 9624592615 555 9876032650 556 10133930246 557 10397715938 558 10668901820 559 10946471840 560 11230870696 561 11523081728 562 11821845254 563 12128522816 564 12443104653 565 12764822204 566 13095420770 567 13433871934 568 13780513172 569 14136604626 570 14500727342 571 14874305427 572 15257526052 573 15649406707 574 16051924310 575 16464071674 576 16886057689 577 17319441556 578 17762652753 579 18217169919 580 18683408800 581 19160155273 582 19649638311 583 20150890734 584 20663965244 585 21190769409 586 21729571566 587 22281889464 588 22848430711 589 23427709205 590 24022221091 591 24631092994 592 25254165915 593 25893743775 594 26547958562 595 27218320702 596 27905896498 597 28608919156 598 29330136621 599 30068828303 600 30824595965 601 31600161461 602 32393549142 603 33206242114 604 34039710361 605 34891896110 606 35765812512 607 36660932358 608 37576583137 609 38515960289 610 39476989661 611 40461095381 612 41470237181 613 42502032329 614 43559760969 615 44643175122 616 45751262926 617 46887742193 618 48050495352 619 49240821495 620 50461255602 621 51709097215 622 52987860712 623 54297668319 624 55637138848 625 57010530645 626 58415743575 627 59853915601 628 61328218743 629 62835644407 630 64379938153 631 65961664132 632 67579037281 633 69236909931 634 70933241648 635 72668963119 636 74447988969 637 76266987355 638 78129920806 639 80037919833 640 81988727236 641 83987835963 642 86033363728 643 88125945104 644 90270344894 645 92462947457 646 94707871521 647 97006947635 648 99357426022 649 101765443385 650 104229386808 651 106749547365 652 109331611909 653 111971728432 654 114674150660 655 117441516532 656 120270561994 657 123168115110 658 126132921118 659 129164868238 660 132270692824 661 135446329279 662 138696127502 663 142023706870 664 145425233131 665 148908258198 666 152472048499 667 156115985359 668 159847976264 669 163663836993 670 167567923549 671 171565017575 672 175650722549 673 179833296865 674 184112705684 675 188487771230 676 192967653701 677 197548160225 678 202233607474 679 207030091703 680 211932668001 681 216950330456 682 222083900759 683 227331583940 684 232703932081 685 238196831846 686 243814500275 687 249564575020 688 255441544156 689 261455151965 690 267607321754 691 273895533831 692 280331867501 693 286912469432 694 293641334063 695 300527878533 696 307566090573 697 314766412950 698 322132140844 699 329659995200 700 337363659907 701 345239749299 702 353291974131 703 361531727907 704 369952582973 705 378565689673 706 387375958560 707 396379316490 708 405591202097 709 415008884676 710 424635713636 711 434485348229 712 444551001468 713 454844517325 714 465372778159 715 476130836164 716 487136019876 717 498386562005 718 509885309009 719 521648480278 720 533669101766 721 545959625074 722 558529286268 723 571372280026 724 584507895478 725 597935675202 726 611657899833 727 625693597727 728 640035813141 729 654697588588 730 669690872832 731 685009036307 732 700673476331 733 716685379754 734 733046392986 735 749778703094 736 766875560972 737 784350565831 738 802218866934 739 820473003748 740 839136617901 741 858213024884 742 877703101371 743 897632553109 744 917995177433 745 938805009709 746 960080927506 747 981814769067 748 1004032470610 749 1026740019715 750 1049937500279 751 1073654432135 752 1097885559319 753 1122645329584 754 1147956841829 755 1173811401630 756 1200237390881 757 1227244003314 758 1254830515236 759 1283030681815 760 1311840588076 761 1341275053461 762 1371362055286 763 1402092511419 764 1433497380135 765 1465589789507 766 1498368137398 767 1531870837426 768 1566095915278 769 1601058438247 770 1636791958032 771 1673287337600 772 1710578153198 773 1748682270287 774 1787597293180 775 1827366648116 776 1867990988910 777 1909485631951 778 1951890370022 779 1995196418890 780 2039440131426 781 2084644919996 782 2130807720301 783 2177977465745 784 2226158148291 785 2275365341170 786 2325645930528 787 2376991896879 788 2429442522642 789 2483027811586 790 2537744119959 791 2593646396418 792 2650742942737 793 2709049516210 794 2768621008997 795 2829450835573 796 2891581258378 797 2955050025983 798 3019853227300 799 3086052246156 800 3153660804626 801 3222694955366 802 3293218465594 803 3365226981898 804 3438765962166 805 3513882065636 806 3590571514819 807 3668902731805 808 3748896016393 809 3830567864216 810 3913992024305 811 3999167219389 812 4086142323279 813 4174974373605 814 4265660132910 815 4358275679073 816 4452849397585 817 4549398326725 818 4648007368369 819 4748679519521 820 4851467205678 821 4956439445309 822 5063594265684 823 5173015938448 824 5284742630064 825 5398792281268 826 5515262089439 827 5634160724774 828 5755544519409 829 5879496118055 830 6006015701763 831 6135196496991 832 6267088249835 833 6401710268010 834 6539173465168 835 6679493698388 836 6822731617558 837 6968985504357 838 7118258659210 839 7270654077401 840 7426235324819 841 7585023543653 842 7747144891563 843 7912624402035 844 8081527394170 845 8253969991087 846 8429960027610 847 8609611006384 848 8793002830826 849 8980159332436 850 9171223411600 851 9366231578115 852 9565254499046 853 9768428407502 854 9975767370381 855 10187396451222 856 10403414563892 857 10623849288614 858 10848862138257 859 11078503602935 860 11312850504442 861 11552061929602 862 11796160056084 863 12045282659774 864 12299550926114 865 12558997349964 866 12823804068689 867 13094038706853 868 13369785069721 869 13651228091302 870 13938400579815 871 14231454159344 872 14530535916604 873 14835684991419 874 15147106183395 875 15464887853708 876 15789122095290 877 16120022816357 878 16457636419884 879 16802129944328 880 17153680272452 881 17512335291222 882 17878324971160 883 18251762361161 884 18632749419307 885 19021532748682 886 19418175663292 887 19822862399476 888 20235804276745 889 20657060298343 890 21086888365195 891 21525431029938 892 21972801845357 893 22429284201222 894 22894962530177 895 23370040123672 896 23854767913654 897 24349219218221 898 24853682718865 899 25368335947316 900 25893306500991 901 26428918859458 902 26975283476213 903 27532625201153 904 28101240137734 905 28681219737204 906 29272886981354 907 29876460389534 908 30492084546799 909 31120130127866 910 31760739092434 911 32414160742636 912 33080742916298 913 33760599538857 914 34454091803455 915 35161486404421 916 35882948247064 917 36618899825295 918 37369521349986 919 38135089746729 920 38916011875675 921 39712429684788 922 40524746757277 923 41353286076381 924 42198237275897 925 43060080684340 926 43939042532953 927 44835431492228 928 45749721345975 929 46682088602286 930 47632984345809 931 48602796791021 932 49591745559596 933 50600375895234 934 51628968766916 935 52677869425000 936 53747627788662 937 54838462373969 938 55950877557971 939 57085337303191 940 58242097239344 941 59421775409476 942 60624717973727 943 61851312189360 944 63102194383764 945 64377634272180 946 65678195844738 947 67004430668275 948 68356638012000 949 69735517243807 950 71141491695532 951 72574997510976 952 74036768602069 953 75527136608290 954 77046732846256 955 78596209559794 956 80175918681389 957 81786650943638 958 83428920265481 959 85103219754531 960 86810393894264 961 88550848451168 962 90325290883952 963 92134489349841 964 93978858809048 965 95859292601398 966 97776411086899 967 99730773554962 968 101723349544789 969 103754633664803 970 105825419357448 971 107936607813904 972 110088689782067 973 112282673566283 974 114519304014747 975 116799218000247 976 119123526024592 977 121492828562278 978 123908016936186 979 126370144324983 980 128879792225437 981 131438098404392 982 134045952432514 983 136704082152063 984 139413757403432 985 142175703874048 986 144990924494972 987 147860646327117 988 150785558800272 989 153766945540123 990 156805864436938 991 159903149663811 992 163060251009449 993 166278042301475 994 169557653590382 995 172900510442457 996 176307430930678 997 179779862755021 998 183319058923134 999 186925978608396 1000 190602274305767