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 3 37 2 38 4 39 3 40 5 41 4 42 6 43 5 44 7 45 6 46 8 47 7 48 10 49 8 50 10 51 9 52 12 53 10 54 12 55 11 56 14 57 12 58 14 59 13 60 17 61 15 62 17 63 16 64 20 65 18 66 20 67 19 68 23 69 21 70 23 71 22 72 27 73 24 74 27 75 25 76 31 77 27 78 31 79 28 80 35 81 30 82 35 83 31 84 41 85 34 86 41 87 36 88 47 89 40 90 49 91 44 92 56 93 48 94 59 95 52 96 68 97 59 98 73 99 64 100 81 101 71 102 86 103 78 104 97 105 87 106 103 107 93 108 115 109 102 110 123 111 111 112 136 113 121 114 143 115 131 116 156 117 143 118 166 119 154 120 181 121 166 122 193 123 178 124 210 125 193 126 223 127 207 128 240 129 224 130 254 131 240 132 276 133 258 134 290 135 274 136 313 137 293 138 330 139 313 140 354 141 333 142 371 143 356 144 398 145 379 146 419 147 402 148 446 149 425 150 469 151 450 152 499 153 477 154 524 155 504 156 556 157 533 158 582 159 562 160 617 161 592 162 644 163 622 164 681 165 655 166 712 167 690 168 752 169 725 170 785 171 763 172 828 173 802 174 866 175 843 176 913 177 886 178 956 179 932 180 1009 181 981 182 1055 183 1031 184 1112 185 1085 186 1163 187 1142 188 1228 189 1202 190 1285 191 1265 192 1358 193 1331 194 1421 195 1402 196 1499 197 1474 198 1570 199 1553 200 1656 201 1634 202 1737 203 1721 204 1832 205 1810 206 1921 207 1905 208 2025 209 2004 210 2122 211 2108 212 2234 213 2217 214 2342 215 2332 216 2468 217 2451 218 2585 219 2576 220 2722 221 2708 222 2853 223 2848 224 3002 225 2990 226 3144 227 3143 228 3307 229 3301 230 3467 231 3468 232 3643 233 3640 234 3818 235 3823 236 4011 237 4014 238 4201 239 4211 240 4411 241 4417 242 4616 243 4632 244 4845 245 4856 246 5068 247 5090 248 5316 249 5333 250 5559 251 5588 252 5827 253 5851 254 6090 255 6126 256 6380 257 6410 258 6664 259 6706 260 6974 261 7013 262 7282 263 7333 264 7620 265 7665 266 7949 267 8007 268 8311 269 8365 270 8666 271 8734 272 9056 273 9115 274 9433 275 9511 276 9853 277 9922 278 10261 279 10349 280 10708 281 10786 282 11147 283 11244 284 11625 285 11714 286 12098 287 12201 288 12608 289 12704 290 13111 291 13223 292 13655 293 13762 294 14191 295 14316 296 14773 297 14892 298 15347 299 15484 300 15970 301 16097 302 16581 303 16728 304 17245 305 17381 306 17894 307 18054 308 18598 309 18749 310 19292 311 19468 312 20044 313 20209 314 20786 315 20972 316 21585 317 21762 318 22376 319 22576 320 23228 321 23421 322 24067 323 24287 324 24975 325 25188 326 25870 327 26112 328 26840 329 27069 330 27797 331 28054 332 28829 333 29074 334 29849 335 30127 336 30946 337 31214 338 32031 339 32333 340 33197 341 33491 342 34357 343 34683 344 35601 345 35918 346 36841 347 37189 348 38169 349 38507 350 39485 351 39862 352 40899 353 41267 354 42301 355 42710 356 43806 357 44203 358 45301 359 45742 360 46908 361 47335 362 48506 363 48977 364 50212 365 50672 366 51914 367 52424 368 53733 369 54233 370 55548 371 56093 372 57482 373 58019 374 59418 375 60004 376 61480 377 62059 378 63541 379 64171 380 65735 381 66359 382 67932 383 68613 384 70272 385 70941 386 72609 387 73339 388 75097 389 75820 390 77590 391 78378 392 80237 393 81015 394 82892 395 83738 396 85713 397 86546 398 88537 399 89441 400 91532 401 92428 402 94534 403 95506 404 97717 405 98682 406 100909 407 101955 408 104295 409 105332 410 107692 411 108813 412 111290 413 112400 414 114900 415 116100 416 118720 417 119911 418 122559 419 123841 420 126609 421 127885 422 130682 423 132054 424 134980 425 136348 426 139307 427 140769 428 143863 429 145326 430 148456 431 150018 432 153291 433 154852 434 158155 435 159824 436 163276 437 164947 438 168436 439 170220 440 173868 441 175648 442 179339 443 181237 444 185091 445 186988 446 190886 447 192909 448 196969 449 198995 450 203102 451 205261 452 209539 453 211706 454 216035 455 218333 456 222843 457 225150 458 229716 459 232162 460 236911 461 239371 462 244181 463 246784 464 251785 465 254403 466 259467 467 262236 468 267498 469 270281 470 275613 471 278555 472 284090 473 287055 474 292668 475 295796 476 301612 477 304766 478 310668 479 313989 480 320108 481 323454 482 329657 483 333175 484 339608 485 343157 486 349680 487 353414 488 360169 489 363931 490 370783 491 374739 492 381833 493 385822 494 393021 495 397211 496 404659 497 408880 498 416437 499 420872 500 428688 501 433162 502 441094 503 445786 504 453982 505 458716 506 467042 507 472002 508 480601 509 485610 510 494339 511 499577 512 508591 513 513884 514 523034 515 528570 516 538019 517 543616 518 553202 519 559054 520 568950 521 574866 522 584913 523 591094 524 601458 525 607703 526 618228 527 624749 528 635614 529 642204 530 653231 531 660110 532 671480 533 678439 534 689979 535 697241 536 709138 537 716482 538 728564 539 736218 540 748673 541 756418 542 769068 543 777134 544 790167 545 798333 546 811565 547 820064 548 833696 549 842306 550 856157 551 865108 552 879374 553 888438 554 902934 555 912355 556 927276 557 936827 558 951987 559 961906 560 977505 561 987571 562 1003421 563 1013863 564 1030177 565 1040773 566 1057349 567 1068334 568 1085390 569 1096540 570 1113870 571 1125428 572 1143259 573 1154990 574 1173108 575 1185269 576 1203903 577 1216245 578 1235185 579 1247972 580 1267442 581 1280422 582 1300218 583 1313667 584 1334010 585 1347668 586 1368352 587 1382493 588 1403742 589 1418107 590 1439719 591 1454584 592 1476780 593 1491882 594 1514464 595 1530075 596 1553268 597 1569136 598 1592733 599 1609131 600 1633357 601 1650029 602 1674669 603 1691899 604 1717198 605 1734717 606 1760455 607 1778554 608 1804973 609 1823372 610 1850259 611 1869257 612 1896855 613 1916171 614 1944249 615 1964193 616 1993014 617 2013293 618 2042615 619 2063549 620 2093642 621 2114924 622 2145548 623 2167509 624 2198935 625 2221261 626 2253242 627 2276284 628 2309088 629 2332519 630 2365903 631 2390077 632 2424319 633 2448906 634 2483757 635 2509109 636 2544854 637 2570636 638 2607028 639 2633607 640 2670921 641 2697962 642 2735943 643 2763810 644 2802747 645 2831108 646 2870744 647 2899959 648 2940596 649 2970335 650 3011694 651 3042314 652 3084716 653 3115889 654 3159047 655 3191139 656 3235379 657 3268045 658 3313070 659 3346700 660 3392856 661 3427086 662 3474067 663 3509293 664 3557442 665 3593302 666 3642314 667 3679211 668 3729431 669 3766995 670 3818125 671 3856766 672 3909147 673 3948490 674 4001819 675 4042278 676 4096908 677 4138107 678 4193731 679 4236074 680 4293047 681 4336177 682 4394196 683 4438511 684 4497927 685 4543067 686 4603560 687 4649935 688 4711882 689 4759124 690 4822197 691 4870720 692 4935298 693 4984733 694 5050493 695 5101258 696 5168583 697 5220300 698 5288853 699 5341945 700 5412116 701 5466209 702 5537663 703 5593188 704 5666329 705 5722893 706 5797364 707 5855421 708 5931640 709 5990787 710 6068394 711 6129090 712 6208498 713 6270332 714 6351193 715 6414640 716 6497367 717 6562004 718 6646246 719 6712551 720 6798735 721 6866277 722 6954039 723 7023319 724 7113082 725 7183663 726 7275082 727 7347454 728 7440946 729 7514679 730 7609895 731 7685481 732 7782845 733 7859859 734 7959004 735 8037938 736 8139320 737 8219749 738 8322975 739 8405405 740 8510948 741 8594931 742 8702397 743 8788448 744 8898322 745 8985979 746 9097855 747 9187659 748 9302029 749 9393509 750 9509956 751 9603670 752 9722699 753 9818159 754 9939344 755 10037122 756 10160974 757 10260574 758 10386678 759 10488679 760 10617540 761 10721436 762 10852637 763 10959016 764 11093073 765 11201437 766 11337920 767 11448849 768 11588291 769 11701288 770 11843247 771 11958901 772 12103924 773 12221734 774 12369375 775 12489933 776 12640740 777 12763539 778 12917061 779 13042709 780 13199507 781 13327511 782 13487117 783 13618061 784 13781054 785 13914445 786 14080355 787 14216797 788 14386224 789 14525200 790 14697650 791 14839773 792 15015870 793 15160627 794 15339861 795 15487891 796 15670879 797 15821653 798 16007881 799 16162042 800 16352160 801 16509173 802 16702662 803 16863178 804 17060692 805 17224158 806 17425170 807 17592267 808 17797434 809 17967602 810 18176404 811 18350322 812 18563402 813 18740523 814 18957385 815 19138373 816 19359668 817 19543983 818 19769187 819 19957501 820 20187287 821 20379063 822 20612896 823 20808810 824 21047379 825 21246894 826 21489651 827 21693451 828 21941101 829 22148632 830 22400625 831 22612585 832 22869644 833 23085468 834 23347019 835 23567429 836 23834221 837 24058633 838 24330084 839 24559255 840 24836101 841 25069428 842 25351095 843 25589350 844 25876579 845 26119149 846 26411385 847 26659040 848 26957031 849 27209155 850 27512325 851 27769711 852 28078831 853 28340854 854 28655328 855 28922799 856 29243405 857 29515687 858 29841848 859 30119756 860 30452250 861 30735146 862 31073397 863 31362101 864 31706897 865 32000780 866 32351515 867 32651409 868 33008915 869 33314186 870 33677832 871 33989316 872 34359947 873 34677004 874 35054003 875 35377474 876 35761696 877 36090933 878 36481729 879 36817601 880 37215877 881 37557720 882 37962780 883 38311489 884 38724270 885 39079164 886 39498965 887 39860966 888 40288733 889 40657128 890 41092171 891 41467917 892 41911173 893 42293550 894 42744339 895 43134302 896 43593569 897 43990412 898 44457466 899 44862140 900 45337951 901 45749760 902 46233627 903 46653515 904 47146413 905 47573705 906 48074941 907 48510578 908 49021130 909 49464439 910 49983595 911 50435524 912 50964326 913 51424209 914 51961891 915 52430674 916 52978307 917 53455323 918 54012142 919 54498374 920 55065463 921 55560198 922 56136789 923 56641048 924 57228230 925 57741294 926 58338313 927 58861216 928 59469159 929 60001180 930 60619279 931 61161460 932 61790828 933 62342454 934 62982335 935 63544463 936 64195969 937 64767852 938 65430225 939 66012957 940 66687318 941 67280155 942 67965762 943 68569799 944 69267770 945 69882254 946 70591851 947 71217897 948 71940259 949 72577130 950 73311494 951 73960307 952 74707826 953 75367834 954 76127760 955 76800114 956 77573615 957 78257557 958 79043885 959 79740556 960 80540904 961 81249559 962 82063142 963 82784944 964 83613002 965 84347199 966 85188911 967 85936704 968 86793356 969 87553943 970 88424705 971 89199355 972 90085519 973 90873386 974 91774129 975 92576523 976 93493140 977 94309202 978 95240881 979 96071946 980 97019997 981 97865208 982 98828815 983 99689502 984 100670011 985 101545314 986 102541890 987 103433168 988 104447159 989 105353567 990 106384161 991 107307044 992 108355617 993 109294146 994 110359827 995 111315362 996 112399602 997 113371319 998 114473204 999 115462479 1000 116583515