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