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