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