0 1 1 1 2 1 3 1 4 1 5 2 6 1 7 2 8 1 9 1 10 1 11 1 12 1 13 2 14 2 15 1 16 1 17 2 18 1 19 3 20 1 21 2 22 2 23 5 24 1 25 1 26 1 27 2 28 1 29 7 30 1 31 9 32 2 33 3 34 2 35 5 36 1 37 11 38 3 39 5 40 1 41 14 42 1 43 15 44 2 45 1 46 6 47 19 48 1 49 1 50 3 51 10 52 2 53 26 54 2 55 13 56 1 57 15 58 12 59 35 60 1 61 39 62 18 63 2 64 1 65 22 66 2 67 50 68 2 69 27 70 2 71 61 72 1 73 67 74 31 75 3 76 3 77 39 78 2 79 87 80 1 81 1 82 49 83 102 84 1 85 55 86 60 87 63 88 1 89 130 90 1 91 74 92 4 93 82 94 88 95 89 96 1 97 178 98 5 99 1 100 1 101 204 102 2 103 224 104 1 105 1 106 149 107 257 108 1 109 278 110 4 111 178 112 1 113 320 114 1 115 212 116 8 117 5 118 246 119 250 120 1 121 1 122 289 123 295 124 9 125 320 126 1 127 522 128 4 129 376 130 3 131 595 132 2 133 444 134 464 135 2 136 6 137 724 138 4 139 776 140 1 141 603 142 629 143 651 144 1 145 694 146 723 147 14 148 18 149 1064 150 2 151 1136 152 8 153 14 154 6 155 1019 156 3 157 1364 158 1131 159 1171 160 1 161 1264 162 1 163 1634 164 21 165 2 166 1513 167 1836 168 1 169 1 170 7 171 26 172 25 173 2192 174 12 175 28 176 1 177 2216 178 2294 179 2601 180 1 181 2761 182 13 183 2724 184 16 185 2906 186 10 187 3116 188 38 189 5 190 15 191 3645 192 1 193 3863 194 3925 195 3 196 1 197 4294 198 3 199 4549 200 2 201 4940 202 5100 203 5266 204 3 205 5628 206 5797 207 55 208 1 209 6391 210 1 211 6262 212 62 213 7263 214 7481 215 7731 216 1 217 8227 218 8469 219 8759 220 2 221 9335 222 31 223 8558 224 2 225 1 226 10880 227 9453 228 4 229 9964 230 32 231 12 232 33 233 11001 234 4 235 14319 236 93 237 15212 238 42 239 12774 240 1 241 13438 242 108 243 113 244 113 245 110 246 44 247 20499 248 48 249 21731 250 41 251 17122 252 1 253 24439 254 25158 255 17 256 1 257 19775 258 42 259 29107 260 2 261 147 262 31741 263 22800 264 1 265 34561 266 53 267 36618 268 170 269 26237 270 1 271 27521 272 1 273 23 274 44651 275 201 276 6 277 31606 278 49945 279 206 280 1 281 34597 282 70 283 36254 284 225 285 31 286 87 287 64103 288 1 289 1 290 82 291 71566 292 258 293 45371 294 9 295 79831 296 102 297 36 298 86640 299 88986 300 1 301 93931 302 96517 303 99132 304 2 305 104577 306 11 307 61826 308 5 309 116390 310 133 311 67379 312 1 313 70433 314 132910 315 1 316 389 317 76683 318 156 319 151629 320 1 321 159764 322 141 323 168356 324 1 325 450 326 182007 327 186843 328 173 329 196745 330 2 331 103287 332 512 333 522 334 223867 335 229662 336 1 337 117082 338 564 339 254383 340 4 341 267734 342 11 343 281638 344 222 345 87 346 303915 347 143830 348 13 349 149946 350 7 351 104 352 5 353 162579 354 243 355 380947 356 744 357 115 358 410572 359 183551 360 1 361 1 362 453356 363 841 364 6 365 488208 366 335 367 215566 368 3 369 916 370 304 371 565716 372 17 373 242826 374 363 375 165 376 376 377 654703 378 2 379 273231 380 13 381 721333 382 739004 383 295320 384 3 385 190 386 813556 387 1214 388 1222 389 331765 390 2 391 917025 392 11 393 961828 394 984970 395 1008648 396 1 397 387152 398 1082937 399 259 400 1 401 417658 402 512 403 1218606 404 1558 405 1 406 605 407 1338538 408 1 409 486245 410 572 411 1469650 412 1756 413 1539736 414 26 415 1612922 416 17 417 1689426 418 659 419 586167 420 1 421 608603 422 1896128 423 2044 424 767 425 2092 426 735 427 2126766 428 2204 429 438 430 860 431 731698 432 1 433 759378 434 827 435 448 436 2481 437 2670392 438 958 439 847188 440 1 441 1 442 927 443 910602 444 38 445 3198176 446 3270689 447 3344982 448 1 449 1014643 450 1 451 3657758 452 3094 453 3824541 454 3910587 455 671 456 1 457 1171154 458 4273397 459 689 460 18 461 1257010 462 1 463 1302825 464 4 465 766 466 5098151 467 1397631 468 2 469 5444879 470 1498 471 5688193 472 1543 473 5942123 474 1515 475 4254 476 31 477 4363 478 6625060 479 1724253 480 1 481 7069791 482 7224432 483 1045 484 1 485 7707673 486 49 487 1980967 488 1919 489 8400070 490 25 491 2121455 492 57 493 9151815 494 2112 495 3 496 5 497 9967399 498 2125 499 2433127 500 41 501 10852236 502 11084986 503 2603598 504 1 505 11811631 506 2353 507 6557 508 6638 509 2881497 510 2 511 13404469 512 5 513 1684 514 14275895 515 14578137 516 73 517 15201209 518 2946 519 15849586 520 1 521 3523070 522 68 523 3643304 524 8178 525 3 526 18334225 527 18717748 528 1 529 1 530 3308 531 8972 532 44 533 21188373 534 3711 535 22078725 536 3724 537 23005092 538 23482273 539 9910 540 1 541 4900916 542 25486457 543 26012630 544 46 545 27095980 546 4 547 5404079 548 11134 549 11244 550 53 551 30612067 552 3 553 31877904 554 32529718 555 3250 556 12323 557 6351011 558 89 559 35984433 560 1 561 3528 562 38222950 563 6993095 564 106 565 40594119 566 41415263 567 2 568 5772 569 7695807 570 1 571 7945947 572 92 573 47627203 574 6339 575 15671 576 1 577 8738436 578 16222 579 53652879 580 77 581 55819464 582 7035 583 58068949 584 7127 585 7 586 61607757 587 10225488 588 2 589 65352233 590 7801 591 67968576 592 7 593 11230572 594 6 595 5881 596 20207 597 76435069 598 8673 599 12328072 600 1 601 12717945 602 8805 603 22034 604 22283 605 22533 606 9652 607 13952032 608 121 609 7229 610 9806 611 100301543 612 1 613 15298808 614 106273902 615 7959 616 2 617 16261123 618 10939 619 16767497 620 138 621 8686 622 123916357 623 126309468 624 1 625 1 626 133758571 627 9304 628 29730 629 141629623 630 1 631 20114137 632 13361 633 152817135 634 155744189 635 158724296 636 200 637 33006 638 14513 639 33861 640 2 641 23373103 642 14957 643 24086483 644 184 645 12147 646 16178 647 25564108 648 1 649 206660094 650 190 651 13094 652 39426 653 27948834 654 17918 655 231213016 656 7 657 41750 658 18374 659 30542630 660 1 661 31460518 662 263404931 663 15633 664 20191 665 15805 666 248 667 288991449 668 47436 669 299880208 670 21937 671 311163543 672 1 673 37514579 674 328856402 675 23 676 1 677 39761874 678 24276 679 360514626 680 1 681 373980316 682 24915 683 43381767 684 2 685 402378630 686 26756 687 417345048 688 9 689 432844934 690 5 691 48700546 692 62433 693 26 694 474055946 695 482738442 696 6 697 500566091 698 509715096 699 519026062 700 1 701 56207579 702 4 703 557930055 704 1 705 27300 706 588934752 707 599630985 708 365 709 63002471 710 36101 711 77241 712 36916 713 667855689 714 9 715 31157 716 81662 717 717423143 718 730358466 719 72578331 720 1 721 770521324 722 87379 723 798470190 724 89337 725 90202 726 418 727 81231014 728 2 729 1 730 45475 731 920339158 732 450 733 88348389 734 970503772 735 40 736 347 737 1023296031 738 448 739 96054196 740 445 741 44193 742 53652 743 101533364 744 5 745 1177946532 746 1198791551 747 114979 748 393 749 1263483535 750 4 751 113422641 752 12 753 1354984722 754 61095 755 1403096766 756 1 757 123188093 758 1478363084 759 55749 760 5 761 130126307 762 67278 763 1612531604 764 138153 765 51 766 1698585279 767 1728237721 768 4 769 145167325 770 3 771 1851925334 772 150623 773 153276249 774 608 775 155515 776 80429 777 69660 778 2089190855 779 2125387232 780 2 781 2199609102 782 86806 783 75604 784 1 785 2355617539 786 90001 787 185244203 788 178558 789 2522264802 790 95656 791 2609795242 792 1 793 2700249527 794 2746603740 795 87455 796 194323 797 211833279 798 6 799 2990124309 800 1 801 204729 802 3146091566 803 3199801533 804 802 805 99697 806 115544 807 3423625899 808 118109 809 248561262 810 1 811 255259466 812 817 813 3787906460 814 127274 815 3917435812 816 1 817 4051235409 818 4119775143 819 88 820 749 821 291299283 822 139810 823 299089910 824 142476 825 100 826 144903 827 315208173 828 2 829 323604661 830 153419 831 5119240740 832 1 833 285687 834 159146 835 5471253872 836 995 837 147872 838 5750478941 839 368747854 840 1 841 1 842 6144240057 843 6246676179 844 320075 845 323301 846 1095 847 330171 848 16 849 6896788757 850 966 851 7127659716 852 1145 853 442185731 854 203042 855 122 856 207395 857 465569854 858 13 859 477739387 860 1238 861 197796 862 8537041259 863 502912788 864 2 865 8965900293 866 9113421724 867 404685 868 1151 869 9570195104 870 10 871 9886905715 872 249282 873 429423 874 253702 875 232634 876 1413 877 601489256 878 11077083764 879 11258021870 880 1 881 632837438 882 2 883 649138960 884 1471 885 263506 886 12606944126 887 682847693 888 16 889 13231689570 890 304711 891 1 892 519726 893 14111375840 894 322110 895 14572143951 896 5 897 302358 898 15290670393 899 15537690441 900 1 901 16043365807 902 352349 903 325821 904 360025 905 17102853123 906 366280 907 878249473 908 608998 909 614971 910 6 911 923215324 912 1 913 19428369399 914 19739711330 915 373856 916 659057 917 20702939820 918 12 919 1019958823 920 6 921 22058153387 922 22410135377 923 22767533762 924 2 925 719479 926 23873111655 927 733988 928 1910 929 1154427195 930 19 931 763309 932 770592 933 26658394419 934 27081091003 935 472641 936 1 937 1274114494 938 525690 939 29293654326 940 2123 941 1338235966 942 553912 943 31188609288 944 22 945 1 946 575404 947 1440312937 948 2488 949 34255055417 950 2511 951 35340526732 952 10 953 1549803663 954 2605 955 37612162713 956 972061 957 609478 958 39407935214 959 40024734174 960 1 961 1 962 687455 963 1040043 964 1049755 965 43926475712 966 15 967 1837100999 968 2881 969 696572 970 751965 971 1928028390 972 2 973 49705046478 974 50477129422 975 383 976 24 977 2072633998 978 821771 979 54514926821 980 2 981 1234133 982 57085787511 983 2227574471 984 27 985 59773784430 986 896802 987 854350 988 3092 989 63548979920 990 2 991 2451525916 992 3480 993 67554455735 994 980166 995 69647764703 996 3604 997 2633390186 998 72905901395 999 979924 1000 15