0 0 1 1 2 1 3 1 4 0 5 3 6 2 7 1 8 1 9 5 10 3 11 0 12 2 13 2 14 5 15 3 16 2 17 0 18 3 19 4 20 5 21 4 22 0 23 3 24 2 25 5 26 5 27 5 28 5 29 0 30 0 31 7 32 2 33 5 34 6 35 5 36 7 37 0 38 2 39 1 40 9 41 2 42 5 43 8 44 6 45 8 46 1 47 2 48 2 49 2 50 10 51 2 52 5 53 12 54 8 55 8 56 1 57 1 58 4 59 2 60 2 61 11 62 3 63 6 64 14 65 9 66 9 67 1 68 1 69 3 70 4 71 2 72 3 73 11 74 4 75 8 76 15 77 12 78 8 79 2 80 2 81 1 82 3 83 6 84 2 85 4 86 11 87 6 88 9 89 18 90 13 91 9 92 1 93 2 94 3 95 1 96 5 97 6 98 2 99 6 100 12 101 6 102 11 103 20 104 14 105 9 106 2 107 1 108 3 109 4 110 1 111 6 112 6 113 2 114 10 115 12 116 8 117 11 118 23 119 16 120 9 121 1 122 2 123 1 124 4 125 5 126 2 127 7 128 7 129 4 130 11 131 13 132 9 133 12 134 24 135 19 136 8 137 1 138 1 139 2 140 2 141 5 142 6 143 2 144 8 145 9 146 4 147 12 148 15 149 10 150 11 151 28 152 21 153 9 154 0 155 1 156 2 157 2 158 2 159 6 160 7 161 3 162 11 163 9 164 5 165 12 166 16 167 11 168 12 169 31 170 22 171 10 172 1 173 0 174 2 175 2 176 2 177 2 178 8 179 10 180 5 181 11 182 11 183 5 184 12 185 17 186 11 187 13 188 35 189 23 190 11 191 1 192 1 193 1 194 2 195 2 196 3 197 3 198 9 199 13 200 6 201 12 202 10 203 6 204 14 205 17 206 10 207 15 208 38 209 26 210 11 211 1 212 1 213 1 214 2 215 3 216 3 217 3 218 5 219 10 220 14 221 8 222 13 223 11 224 5 225 15 226 19 227 11 228 17 229 38 230 30 231 11 232 1 233 1 234 2 235 1 236 3 237 2 238 6 239 4 240 5 241 11 242 18 243 8 244 12 245 13 246 6 247 16 248 21 249 11 250 19 251 39 252 32 253 12 254 1 255 2 256 1 257 3 258 2 259 3 260 3 261 5 262 6 263 6 264 12 265 20 266 8 267 12 268 14 269 6 270 20 271 21 272 12 273 21 274 42 275 33 276 11 277 2 278 1 279 4 280 3 281 3 282 2 283 4 284 3 285 4 286 6 287 8 288 15 289 20 290 9 291 13 292 15 293 6 294 22 295 22 296 14 297 25 298 43 299 35 300 11 301 1 302 2 303 3 304 4 305 4 306 3 307 2 308 4 309 4 310 6 311 6 312 8 313 17 314 21 315 8 316 15 317 16 318 6 319 25 320 22 321 19 322 26 323 46 324 35 325 12 326 2 327 1 328 2 329 4 330 5 331 4 332 5 333 2 334 4 335 5 336 8 337 6 338 7 339 17 340 23 341 8 342 13 343 21 344 6 345 27 346 25 347 22 348 27 349 48 350 37 351 12 352 2 353 3 354 1 355 3 356 5 357 6 358 5 359 4 360 3 361 5 362 4 363 8 364 7 365 8 366 17 367 22 368 10 369 14 370 20 371 10 372 27 373 28 374 24 375 30 376 51 377 37 378 12 379 3 380 2 381 3 382 2 383 3 384 7 385 6 386 5 387 5 388 2 389 7 390 4 391 7 392 8 393 9 394 18 395 21 396 11 397 16 398 23 399 10 400 31 401 29 402 25 403 33 404 54 405 39 406 11 407 2 408 3 409 2 410 4 411 3 412 4 413 6 414 8 415 5 416 4 417 4 418 6 419 6 420 7 421 7 422 9 423 19 424 23 425 11 426 17 427 24 428 14 429 31 430 33 431 28 432 37 433 55 434 40 435 12 436 1 437 3 438 3 439 2 440 4 441 4 442 6 443 6 444 7 445 6 446 5 447 3 448 8 449 5 450 8 451 8 452 8 453 20 454 25 455 11 456 16 457 28 458 15 459 37 460 32 461 33 462 37 463 59 464 40 465 13 466 2 467 1 468 4 469 4 470 2 471 5 472 3 473 6 474 7 475 7 476 6 477 6 478 3 479 7 480 7 481 8 482 9 483 9 484 19 485 26 486 12 487 17 488 29 489 19 490 39 491 38 492 32 493 42 494 57 495 43 496 13 497 3 498 2 499 2 500 4 501 3 502 4 503 5 504 4 505 5 506 7 507 8 508 6 509 7 510 4 511 8 512 6 513 9 514 8 515 11 516 20 517 26 518 13 519 20 520 30 521 21 522 42 523 38 524 41 525 41 526 62 527 39 528 14 529 3 530 3 531 3 532 2 533 5 534 3 535 4 536 6 537 3 538 6 539 6 540 9 541 9 542 7 543 3 544 9 545 6 546 8 547 10 548 11 549 21 550 27 551 12 552 23 553 34 554 22 555 45 556 40 557 41 558 52 559 60 560 42 561 11 562 4 563 3 564 3 565 3 566 2 567 4 568 5 569 4 570 6 571 4 572 6 573 8 574 9 575 9 576 8 577 3 578 9 579 7 580 8 581 9 582 12 583 22 584 29 585 13 586 25 587 36 588 25 589 48 590 40 591 45 592 55 593 66 594 40 595 13 596 1 597 4 598 3 599 3 600 4 601 3 602 4 603 4 604 5 605 7 606 4 607 7 608 8 609 10 610 8 611 9 612 4 613 8 614 7 615 9 616 9 617 13 618 24 619 28 620 14 621 30 622 37 623 26 624 49 625 41 626 52 627 58 628 65 629 46 630 11 631 3 632 1 633 4 634 3 635 3 636 4 637 4 638 6 639 4 640 5 641 8 642 4 643 7 644 9 645 10 646 9 647 7 648 5 649 9 650 6 651 10 652 11 653 14 654 23 655 32 656 15 657 33 658 40 659 26 660 49 661 44 662 56 663 63 664 65 665 45 666 16 667 1 668 3 669 1 670 5 671 4 672 3 673 4 674 3 675 6 676 6 677 6 678 8 679 5 680 7 681 9 682 10 683 9 684 8 685 4 686 10 687 8 688 9 689 13 690 16 691 22 692 32 693 19 694 34 695 43 696 30 697 51 698 45 699 59 700 64 701 67 702 47 703 14 704 6 705 1 706 3 707 2 708 5 709 5 710 3 711 5 712 3 713 6 714 5 715 8 716 8 717 5 718 8 719 9 720 10 721 10 722 9 723 4 724 9 725 10 726 10 727 12 728 17 729 25 730 30 731 23 732 39 733 45 734 29 735 57 736 48 737 59 738 67 739 66 740 50 741 15 742 4 743 6 744 1 745 3 746 2 747 5 748 5 749 3 750 6 751 4 752 5 753 6 754 8 755 10 756 5 757 9 758 10 759 9 760 9 761 11 762 4 763 11 764 9 765 12 766 13 767 16 768 26 769 34 770 24 771 43 772 48 773 28 774 57 775 56 776 60 777 69 778 67 779 49 780 16 781 5 782 4 783 6 784 1 785 3 786 3 787 5 788 5 789 3 790 6 791 4 792 7 793 4 794 10 795 10 796 7 797 9 798 10 799 10 800 8 801 10 802 6 803 10 804 13 805 12 806 14 807 18 808 25 809 34 810 31 811 43 812 49 813 33 814 59 815 56 816 67 817 69 818 68 819 50 820 14 821 6 822 5 823 4 824 6 825 1 826 3 827 4 828 6 829 5 830 4 831 6 832 4 833 6 834 6 835 8 836 13 837 7 838 10 839 10 840 10 841 9 842 8 843 6 844 13 845 11 846 13 847 17 848 22 849 26 850 33 851 34 852 45 853 50 854 34 855 69 856 57 857 68 858 75 859 64 860 52 861 14 862 4 863 6 864 5 865 4 866 6 867 1 868 3 869 6 870 7 871 6 872 4 873 6 874 4 875 6 876 4 877 11 878 11 879 9 880 10 881 12 882 11 883 9 884 9 885 4 886 12 887 14 888 11 889 20 890 23 891 29 892 38 893 33 894 49 895 50 896 35 897 76 898 61 899 73 900 72 901 69 902 49 903 15 904 4 905 4 906 6 907 5 908 5 909 6 910 1 911 4 912 6 913 8 914 6 915 5 916 6 917 6 918 7 919 4 920 8 921 13 922 7 923 13 924 12 925 11 926 11 927 9 928 5 929 11 930 12 931 15 932 17 933 26 934 32 935 42 936 34 937 47 938 53 939 35 940 81 941 67 942 80 943 72 944 65 945 55 946 11 947 5 948 5 949 4 950 6 951 5 952 5 953 6 954 2 955 6 956 7 957 8 958 6 959 5 960 7 961 5 962 7 963 6 964 9 965 9 966 9 967 11 968 15 969 11 970 12 971 10 972 5 973 12 974 11 975 15 976 20 977 23 978 35 979 47 980 37 981 51 982 52 983 40 984 85 985 72 986 83 987 74 988 67 989 51 990 16 991 1 992 5 993 5 994 4 995 7 996 6 997 5 998 8 999 1 1000 7