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