1 0 2 0 3 0 4 0 5 0 6 0 7 1 8 1 9 1 10 1 11 1 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 1 25 1 26 1 27 1 28 2 29 1 30 1 31 1 32 2 33 1 34 1 35 2 36 3 37 2 38 2 39 3 40 4 41 3 42 3 43 4 44 5 45 4 46 4 47 5 48 6 49 5 50 5 51 6 52 7 53 6 54 6 55 7 56 8 57 7 58 7 59 8 60 9 61 8 62 8 63 10 64 10 65 9 66 9 67 10 68 11 69 10 70 11 71 12 72 14 73 12 74 12 75 13 76 14 77 13 78 13 79 15 80 16 81 16 82 15 83 16 84 17 85 16 86 16 87 17 88 19 89 18 90 19 91 20 92 20 93 19 94 19 95 21 96 21 97 21 98 22 99 25 100 25 101 23 102 24 103 26 104 27 105 25 106 27 107 30 108 32 109 30 110 30 111 33 112 35 113 33 114 33 115 37 116 39 117 39 118 39 119 42 120 44 121 43 122 44 123 46 124 49 125 49 126 51 127 53 128 55 129 54 130 55 131 58 132 59 133 60 134 62 135 67 136 68 137 67 138 69 139 72 140 75 141 73 142 76 143 80 144 85 145 82 146 83 147 88 148 91 149 90 150 91 151 98 152 102 153 102 154 103 155 107 156 112 157 110 158 112 159 116 160 123 161 121 162 124 163 129 164 133 165 132 166 134 167 141 168 145 169 145 170 148 171 155 172 160 173 157 174 160 175 168 176 173 177 169 178 173 179 181 180 188 181 185 182 189 183 198 184 205 185 202 186 204 187 213 188 221 189 219 190 221 191 230 192 238 193 235 194 237 195 245 196 254 197 252 198 257 199 266 200 276 201 272 202 276 203 286 204 292 205 290 206 294 207 309 208 315 209 312 210 317 211 330 212 337 213 332 214 340 215 354 216 365 217 359 218 366 219 380 220 389 221 384 222 388 223 406 224 415 225 414 226 417 227 434 228 445 229 440 230 447 231 462 232 478 233 472 234 482 235 498 236 511 237 506 238 514 239 533 240 543 241 541 242 548 243 571 244 582 245 579 246 589 247 611 248 625 249 617 250 631 251 651 252 669 253 662 254 672 255 697 256 712 257 709 258 715 259 744 260 760 261 759 262 768 263 796 264 815 265 811 266 823 267 845 268 867 269 863 270 878 271 904 272 925 273 924 274 936 275 966 276 981 277 983 278 998 279 1030 280 1051 281 1050 282 1069 283 1098 284 1121 285 1116 286 1136 287 1170 288 1197 289 1193 290 1212 291 1249 292 1272 293 1272 294 1289 295 1331 296 1357 297 1360 298 1379 299 1418 300 1448 301 1446 302 1467 303 1506 304 1536 305 1537 306 1562 307 1604 308 1634 309 1638 310 1663 311 1707 312 1736 313 1742 314 1767 315 1817 316 1847 317 1850 318 1878 319 1928 320 1961 321 1961 322 1995 323 2046 324 2086 325 2088 326 2120 327 2175 328 2214 329 2217 330 2246 331 2308 332 2347 333 2356 334 2386 335 2449 336 2489 337 2496 338 2531 339 2588 340 2636 341 2643 342 2685 343 2747 344 2794 345 2803 346 2841 347 2909 348 2950 349 2965 350 3008 351 3083 352 3126 353 3139 354 3182 355 3253 356 3305 357 3314 358 3367 359 3443 360 3505 361 3511 362 3560 363 3641 364 3695 365 3710 366 3755 367 3846 368 3902 369 3925 370 3971 371 4058 372 4121 373 4138 374 4194 375 4281 376 4350 377 4368 378 4432 379 4518 380 4582 381 4606 382 4667 383 4764 384 4825 385 4858 386 4920 387 5025 388 5090 389 5115 390 5187 391 5289 392 5365 393 5385 394 5465 395 5570 396 5652 397 5675 398 5749 399 5865 400 5946 401 5976 402 6047 403 6173 404 6253 405 6292 406 6370 407 6493 408 6582 409 6617 410 6703 411 6820 412 6917 413 6955 414 7048 415 7175 416 7268 417 7310 418 7401 419 7537 420 7627 421 7677 422 7777 423 7925 424 8022 425 8068 426 8170 427 8315 428 8421 429 8458 430 8572 431 8726 432 8849 433 8889 434 9002 435 9163 436 9279 437 9329 438 9439 439 9614 440 9737 441 9803 442 9914 443 10086 444 10214 445 10271 446 10393 447 10564 448 10709 449 10769 450 10911 451 11086 452 11226 453 11292 454 11426 455 11621 456 11753 457 11837 458 11976 459 12188 460 12328 461 12401 462 12551 463 12758 464 12914 465 12980 466 13148 467 13360 468 13537 469 13609 470 13771 471 13998 472 14168 473 14257 474 14409 475 14658 476 14832 477 14936 478 15098 479 15338 480 15529 481 15622 482 15806 483 16041 484 16252 485 16351 486 16550 487 16803 488 17005 489 17115 490 17309 491 17583 492 17773 493 17901 494 18104 495 18399 496 18605 497 18724 498 18945 499 19233 500 19464 501 19569 502 19810 503 20113 504 20361 505 20479 506 20710 507 21036 508 21273 509 21415 510 21640 511 21987 512 22239 513 22396 514 22636 515 22974 516 23248 517 23392 518 23662 519 23995 520 24289 521 24444 522 24730 523 25086 524 25367 525 25547 526 25824 527 26209 528 26483 529 26675 530 26971 531 27375 532 27677 533 27854 534 28178 535 28580 536 28903 537 29073 538 29413 539 29838 540 30181 541 30372 542 30701 543 31156 544 31495 545 31706 546 32036 547 32510 548 32874 549 33102 550 33460 551 33927 552 34316 553 34539 554 34911 555 35382 556 35787 557 36033 558 36431 559 36935 560 37340 561 37599 562 38001 563 38525 564 38925 565 39204 566 39632 567 40192 568 40616 569 40889 570 41336 571 41900 572 42344 573 42615 574 43092 575 43688 576 44167 577 44454 578 44930 579 45542 580 46026 581 46337 582 46815 583 47464 584 47972 585 48317 586 48808 587 49462 588 49993 589 50334 590 50859 591 51514 592 52079 593 52438 594 53001 595 53684 596 54250 597 54629 598 55200 599 55923 600 56484 601 56895 602 57490 603 58256 604 58834 605 59245 606 59868 607 60648 608 61268 609 61670 610 62336 611 63137 612 63804 613 64221 614 64889 615 65732 616 66405 617 66858 618 67518 619 68406 620 69099 621 69596 622 70279 623 71185 624 71919 625 72413 626 73141 627 74037 628 74816 629 75323 630 76111 631 77040 632 77827 633 78370 634 79157 635 80139 636 80907 637 81504 638 82316 639 83360 640 84164 641 84755 642 85611 643 86656 644 87514 645 88086 646 89005 647 90083 648 91004 649 91603 650 92521 651 93654 652 94565 653 95220 654 96121 655 97327 656 98271 657 98981 658 99925 659 101130 660 102130 661 102822 662 103834 663 105033 664 106093 665 106823 666 107889 667 109138 668 110194 669 110973 670 112036 671 113360 672 114411 673 115250 674 116361 675 117748 676 118848 677 119673 678 120848 679 122240 680 123409 681 124221 682 125461 683 126905 684 128134 685 128995 686 130235 687 131758 688 132990 689 133908 690 135148 691 136737 692 138016 693 139000 694 140294 695 141897 696 143244 697 144219 698 145583 699 147188 700 148609 701 149628 702 151064 703 152741 704 154162 705 155246 706 156687 707 158446 708 159862 709 161016 710 162520 711 164357 712 165840 713 166990 714 168567 715 170414 716 171971 717 173114 718 174777 719 176692 720 178331 721 179538 722 181205 723 183208 724 184850 725 186133 726 187806 727 189902 728 191612 729 192963 730 194706 731 196813 732 198606 733 199954 734 201789 735 203924 736 205805 737 207216 738 209134 739 211350 740 213238 741 214723 742 216665 743 218984 744 220879 745 222448 746 224462 747 226869 748 228849 749 230430 750 232539 751 234980 752 237056 753 238634 754 240834 755 243356 756 245525 757 247185 758 249411 759 252044 760 254234 761 255980 762 258217 763 260957 764 263219 765 265064 766 267391 767 270172 768 272542 769 274390 770 276834 771 279628 772 282102 773 284027 774 286584 775 289495 776 291994 777 294023 778 296597 779 299622 780 302126 781 304260 782 306931 783 310083 784 312707 785 314860 786 317650 787 320828 788 323567 789 325718 790 328636 791 331930 792 334785 793 337046 794 339985 795 343417 796 346284 797 348662 798 351640 799 355214 800 358200 801 360684 802 363785 803 367389 804 370501 805 373002 806 376240 807 379900 808 383143 809 385748 810 389108 811 392905 812 396180 813 398912 814 402313 815 406270 816 409581 817 412435 818 415963 819 420049 820 423503 821 426383 822 430061 823 434216 824 437813 825 440727 826 444544 827 448834 828 452558 829 455601 830 459471 831 463932 832 467716 833 470905 834 474831 835 479441 836 483356 837 486675 838 490756 839 495436 840 499524 841 502885 842 507122 843 511868 844 516090 845 519583 846 523975 847 528914 848 533209 849 536862 850 541335 851 546440 852 550784 853 554575 854 559207 855 564489 856 569007 857 572865 858 577667 859 583038 860 587723 861 591631 862 596609 863 602166 864 607025 865 611099 866 616159 867 621904 868 626850 869 631084 870 636233 871 642169 872 647288 873 651701 874 657021 875 663074 876 668375 877 672859 878 678376 879 684528 880 690026 881 694666 882 700404 883 706753 884 712348 885 717175 886 723017 887 729592 888 735265 889 740294 890 746312 891 753113 892 758975 893 764095 894 770322 895 777256 896 783352 897 788538 898 795015 899 802144 900 808472 901 813844 902 820432 903 827814 904 834237 905 839844 906 846515 907 854157 908 860772 909 866604 910 873512 911 881289 912 888167 913 894086 914 901264 915 909142 916 916262 917 922385 918 929819 919 937962 920 945199 921 951574 922 959117 923 967558 924 974892 925 981522 926 989308 927 998025 928 1005631 929 1012349 930 1020429 931 1029282 932 1037186 933 1043997 934 1052364 935 1061504 936 1069667 937 1076740 938 1085234 939 1094692 940 1102977 941 1110337 942 1118971 943 1128739 944 1137301 945 1144926 946 1153860 947 1163773 948 1172666 949 1180410 950 1189681 951 1199767 952 1208949 953 1216965 954 1226510 955 1236929 956 1246237 957 1254585 958 1264296 959 1275087 960 1284568 961 1293203 962 1303239 963 1314333 964 1324148 965 1332905 966 1343312 967 1354610 968 1364770 969 1373681 970 1384411 971 1396057 972 1406517 973 1415781 974 1426681 975 1438744 976 1449395 977 1458990 978 1470099 979 1482490 980 1493508 981 1503403 982 1514908 983 1527504 984 1538907 985 1548995 986 1560856 987 1573704 988 1585438 989 1595890 990 1608106 991 1621384 992 1633317 993 1644138 994 1656603 995 1670272 996 1682444 997 1693603 998 1706501 999 1720572 1000 1733163