1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 2 25 1 26 2 27 1 28 2 29 1 30 2 31 1 32 2 33 1 34 2 35 1 36 4 37 2 38 4 39 4 40 5 41 4 42 7 43 5 44 7 45 7 46 8 47 7 48 11 49 9 50 11 51 12 52 13 53 12 54 16 55 14 56 16 57 17 58 18 59 17 60 22 61 19 62 22 63 23 64 24 65 23 66 28 67 25 68 28 69 29 70 30 71 29 72 36 73 32 74 36 75 38 76 40 77 40 78 48 79 45 80 50 81 53 82 56 83 57 84 67 85 65 86 71 87 75 88 79 89 81 90 92 91 91 92 98 93 103 94 108 95 111 96 124 97 123 98 132 99 137 100 144 101 147 102 162 103 161 104 172 105 177 106 186 107 189 108 208 109 206 110 220 111 226 112 237 113 240 114 263 115 260 116 277 117 284 118 297 119 300 120 329 121 324 122 344 123 353 124 368 125 371 126 404 127 399 128 422 129 433 130 451 131 453 132 493 133 486 134 513 135 526 136 545 137 548 138 593 139 584 140 616 141 630 142 652 143 655 144 708 145 696 146 733 147 750 148 775 149 778 150 840 151 826 152 870 153 891 154 921 155 925 156 998 157 983 158 1035 159 1061 160 1097 161 1103 162 1187 163 1173 164 1234 165 1265 166 1309 167 1318 168 1415 169 1403 170 1474 171 1512 172 1564 173 1578 174 1688 175 1678 176 1761 177 1806 178 1868 179 1888 180 2013 181 2006 182 2102 183 2156 184 2228 185 2254 186 2395 187 2392 188 2502 189 2566 190 2650 191 2683 192 2843 193 2845 194 2970 195 3045 196 3143 197 3185 198 3364 199 3374 200 3516 201 3603 202 3718 203 3770 204 3970 205 3989 206 4150 207 4251 208 4383 209 4448 210 4670 211 4699 212 4882 213 4998 214 5149 215 5228 216 5475 217 5515 218 5721 219 5854 220 6026 221 6119 222 6394 223 6446 224 6677 225 6828 226 7024 227 7132 228 7438 229 7503 230 7762 231 7932 232 8155 233 8279 234 8618 235 8697 236 8987 237 9177 238 9430 239 9571 240 9948 241 10041 242 10365 243 10577 244 10862 245 11021 246 11437 247 11547 248 11908 249 12143 250 12464 251 12642 252 13103 253 13230 254 13631 255 13890 256 14250 257 14448 258 14955 259 15100 260 15546 261 15829 262 16232 263 16451 264 17010 265 17173 266 17667 267 17977 268 18428 269 18669 270 19284 271 19468 272 20016 273 20355 274 20858 275 21124 276 21802 277 22009 278 22615 279 22987 280 23549 281 23842 282 24587 283 24821 284 25492 285 25898 286 26524 287 26849 288 27669 289 27933 290 28675 291 29121 292 29819 293 30180 294 31080 295 31379 296 32201 297 32690 298 33466 299 33869 300 34859 301 35196 302 36105 303 36643 304 37506 305 37954 306 39040 307 39423 308 40428 309 41020 310 41978 311 42479 312 43673 313 44107 314 45216 315 45870 316 46935 317 47495 318 48804 319 49299 320 50524 321 51245 322 52426 323 53053 324 54489 325 55050 326 56399 327 57197 328 58505 329 59206 330 60778 331 61415 332 62902 333 63784 334 65229 335 66014 336 67737 337 68457 338 70092 339 71069 340 72666 341 73541 342 75426 343 76239 344 78036 345 79115 346 80874 347 81851 348 83913 349 84827 350 86798 351 87992 352 89929 353 91017 354 93268 355 94295 356 96457 357 97775 358 99902 359 101114 360 103573 361 104720 362 107086 363 108541 364 110874 365 112219 366 114896 367 116179 368 118766 369 120368 370 122922 371 124414 372 127330 373 128758 374 131581 375 133344 376 136136 377 137788 378 140955 379 142543 380 145624 381 147556 382 150603 383 152429 384 155868 385 157626 386 160977 387 163098 388 166419 389 168431 390 172160 391 174105 392 177751 393 180073 394 183687 395 185902 396 189942 397 192090 398 196046 399 198587 400 202519 401 204948 402 209318 403 211687 404 215977 405 218749 406 223015 407 225681 408 230404 409 233009 410 237654 411 240678 412 245305 413 248224 414 253321 415 256181 416 261206 417 264500 418 269507 419 272700 420 278201 421 281329 422 286756 423 290342 424 295755 425 299236 426 305158 427 308582 428 314437 429 318333 430 324177 431 327970 432 334347 433 338085 434 344392 435 348620 436 354924 437 359051 438 365902 439 369980 440 376772 441 381349 442 388140 443 392626 444 399983 445 404417 446 411718 447 416673 448 423980 449 428847 450 436737 451 441555 452 449401 453 454757 454 462607 455 467882 456 476340 457 481566 458 489982 459 495770 460 504200 461 509900 462 518958 463 524621 464 533640 465 539879 466 548917 467 555077 468 564768 469 570894 470 580549 471 587270 472 596958 473 603601 474 613956 475 620573 476 630903 477 638133 478 648500 479 655661 480 666723 481 673853 482 684895 483 692667 484 703750 485 711451 486 723253 487 730932 488 742724 489 751066 490 762906 491 771181 492 783772 493 792028 494 804609 495 813553 496 826193 497 835074 498 848488 499 857358 500 870776 501 880347 502 893832 503 903354 504 917636 505 927146 506 941441 507 951679 508 966051 509 976246 510 991441 511 1001628 512 1016854 513 1027791 514 1043096 515 1053999 516 1070159 517 1081058 518 1097258 519 1108933 520 1125228 521 1136868 522 1154044 523 1165695 524 1182920 525 1195366 526 1212699 527 1225123 528 1243369 529 1255812 530 1274119 531 1287379 532 1305815 533 1319061 534 1338431 535 1351706 536 1371155 537 1385274 538 1404863 539 1418980 540 1439543 541 1453687 542 1474339 543 1489363 544 1510166 545 1525191 546 1547002 547 1562070 548 1583987 549 1599965 550 1622049 551 1638033 552 1661169 553 1677207 554 1700452 555 1717433 556 1740866 557 1757863 558 1782383 559 1799447 560 1824102 561 1842132 562 1866990 563 1885057 564 1911039 565 1929177 566 1955311 567 1974457 568 2000814 569 2020009 570 2047532 571 2066806 572 2094511 573 2114830 574 2142766 575 2163151 576 2192301 577 2212775 578 2242125 579 2263685 580 2293293 581 2314924 582 2345789 583 2367532 584 2398618 585 2421478 586 2452843 587 2475799 588 2508469 589 2531550 590 2564467 591 2588699 592 2621926 593 2646275 594 2680841 595 2705334 596 2740183 597 2765866 598 2801047 599 2826875 600 2863449 601 2889425 602 2926313 603 2953529 604 2990769 605 3018147 606 3056830 607 3084384 608 3123417 609 3152253 610 3191668 611 3220686 612 3261602 613 3290817 614 3332105 615 3362647 616 3404354 617 3435106 618 3478363 619 3509341 620 3553014 621 3585350 622 3629476 623 3662060 624 3707782 625 3740611 626 3786787 627 3821027 628 3867694 629 3902211 630 3950532 631 3985318 632 4034142 633 4070388 634 4119731 635 4156286 636 4207345 637 4244201 638 4295801 639 4334169 640 4386337 641 4425034 642 4478980 643 4518021 644 4572545 645 4613144 646 4668280 647 4709248 648 4766227 649 4807572 650 4865175 651 4908128 652 4966398 653 5009756 654 5069925 655 5113697 656 5174541 657 5219982 658 5281538 659 5327421 660 5390956 661 5437277 662 5501532 663 5549594 664 5614604 665 5663139 666 5730203 667 5779226 668 5847063 669 5897891 670 5966537 671 6017870 672 6088657 673 6140521 674 6212118 675 6265854 676 6338320 677 6392608 678 6467291 679 6522156 680 6597717 681 6654509 682 6730991 683 6788391 684 6867166 685 6925179 686 7004892 687 7064915 688 7145609 689 7206289 690 7289363 691 7350696 692 7434782 693 7498202 694 7583312 695 7647443 696 7735028 697 7799861 698 7888520 699 7955521 700 8045278 701 8113031 702 8205353 703 8273872 704 8367333 705 8438090 706 8532713 707 8604294 708 8701578 709 8773975 710 8872473 711 8947184 712 9046925 713 9122524 714 9225006 715 9301482 716 9405263 717 9484136 718 9589227 719 9669059 720 9777000 721 9857753 722 9967074 723 10050323 724 10161024 725 10245291 726 10358943 727 10444210 728 10559330 729 10647176 730 10763760 731 10852691 732 10972339 733 11062339 734 11183527 735 11276201 736 11398946 737 11492783 738 11618695 739 11713681 740 11841235 741 11938969 742 12068171 743 12167160 744 12299629 745 12399833 746 12534039 747 12637104 748 12773054 749 12877451 750 13016788 751 13122476 752 13263655 753 13372305 754 13515311 755 13625379 756 13771898 757 13883345 758 14031802 759 14146323 760 14296720 761 14412726 762 14566762 763 14684251 764 14840316 765 14960980 766 15119093 767 15241344 768 15403227 769 15527049 770 15691073 771 15818182 772 15984374 773 16113163 774 16283247 775 16413704 776 16586043 777 16719914 778 16894530 779 17030179 780 17208840 781 17346235 782 17527266 783 17668218 784 17851631 785 17994452 786 18182058 787 18326739 788 18516835 789 18665201 790 18857804 791 19008137 792 19205095 793 19357393 794 19556950 795 19713071 796 19915261 797 20073467 798 20280165 799 20440442 800 20649886 801 20814106 802 21026306 803 21192745 804 21409602 805 21578211 806 21797954 807 21970668 808 22193298 809 22368352 810 22595810 811 22773137 812 23003638 813 23185221 814 23418723 815 23602777 816 23841279 817 24027731 818 24269423 819 24460284 820 24705134 821 24898579 822 25148597 823 25344582 824 25597935 825 25798471 826 26055129 827 26258408 828 26520410 829 26726356 830 26991861 831 27202504 832 27471481 833 27685017 834 27959493 835 28175837 836 28453988 837 28675194 838 28956974 839 29181226 840 29468705 841 29695885 842 29987210 843 30219439 844 30514549 845 30749965 846 31050960 847 31289477 848 31594497 849 31838227 850 32147213 851 32394275 852 32709356 853 32959681 854 33278942 855 33534663 856 33858076 857 34117294 858 34446999 859 34709648 860 35043733 861 35311936 862 35650363 863 35922249 864 36267163 865 36542635 866 36892116 867 37173356 868 37527375 869 37812460 870 38173190 871 38462023 872 38827527 873 39122332 874 39492548 875 39791378 876 40168536 877 40471299 878 40853428 879 41162377 880 41549435 881 41862559 882 42256797 883 42574060 884 42973456 885 43297106 886 43701638 887 44029673 888 44441629 889 44773984 890 45191320 891 45530270 892 45952969 893 46296502 894 46726848 895 47074898 896 47510847 897 47865729 898 48307259 899 48666928 900 49116375 901 49480728 902 49936013 903 50307457 904 50768525 905 51144953 906 51614198 907 51995536 908 52470859 909 52859521 910 53340869 911 53734716 912 54224526 913 54623500 914 55119608 915 55526157 916 56028526 917 56440499 918 56951605 919 57368919 920 57886593 921 58311703 922 58835890 923 59266682 924 59799864 925 60236209 926 60776220 927 61220642 928 61767420 929 62217759 930 62773829 931 63229934 932 63793123 933 64257577 934 64827767 935 65298389 936 65878164 937 66354805 938 66941980 939 67427236 940 68021699 941 68513350 942 69117702 943 69615646 944 70227663 945 70734486 946 71354072 947 71867581 948 72497367 949 73017422 950 73655176 951 74184372 952 74830006 953 75366169 954 76022286 955 76565265 956 77229651 957 77782079 958 78454647 959 79014316 960 79697712 961 80264442 962 80956419 963 81532926 964 82233372 965 82817390 966 83528995 967 84120392 968 84840898 969 85442374 970 86171681 971 86780933 972 87521769 973 88138709 974 88888730 975 89516077 976 90275226 977 90910662 978 91681700 979 92325123 980 93105699 981 93759829 982 94549880 983 95212433 984 96014720 985 96685559 986 97497715 987 98179645 988 99001628 989 99692280 990 100526895 991 101226129 992 102070987 993 102781685 994 103636687 995 104356436 996 105224465 997 105953140 998 106831772 999 107572279 1000 108461438