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