1 0 2 0 3 0 4 0 5 0 6 0 7 1 8 0 9 1 10 0 11 2 12 0 13 2 14 2 15 3 16 2 17 3 18 3 19 5 20 3 21 7 22 4 23 8 24 5 25 9 26 7 27 10 28 8 29 11 30 9 31 14 32 11 33 16 34 12 35 18 36 14 37 19 38 17 39 21 40 18 41 23 42 21 43 27 44 22 45 30 46 24 47 32 48 27 49 34 50 30 51 37 52 33 53 40 54 35 55 44 56 37 57 47 58 40 59 50 60 44 61 53 62 49 63 56 64 52 65 60 66 55 67 64 68 57 69 68 70 61 71 71 72 66 73 77 74 70 75 80 76 74 77 85 78 77 79 90 80 80 81 95 82 86 83 100 84 90 85 103 86 96 87 107 88 100 89 113 90 104 91 119 92 110 93 124 94 116 95 129 96 121 97 133 98 126 99 138 100 132 101 146 102 136 103 153 104 141 105 158 106 148 107 164 108 153 109 168 110 160 111 176 112 165 113 184 114 172 115 190 116 177 117 196 118 185 119 203 120 191 121 208 122 199 123 217 124 205 125 223 126 210 127 231 128 216 129 238 130 226 131 246 132 233 133 252 134 241 135 262 136 247 137 269 138 254 139 276 140 262 141 285 142 271 143 292 144 280 145 298 146 288 147 309 148 295 149 317 150 303 151 325 152 312 153 333 154 321 155 342 156 329 157 350 158 337 159 363 160 345 161 371 162 354 163 382 164 363 165 390 166 373 167 398 168 381 169 405 170 392 171 420 172 401 173 428 174 410 175 438 176 420 177 446 178 431 179 456 180 440 181 466 182 451 183 479 184 461 185 490 186 470 187 500 188 482 189 510 190 494 191 519 192 503 193 533 194 513 195 544 196 523 197 553 198 533 199 565 200 548 201 576 202 560 203 587 204 570 205 600 206 581 207 611 208 590 209 623 210 602 211 637 212 617 213 647 214 628 215 659 216 638 217 674 218 649 219 687 220 661 221 699 222 675 223 711 224 689 225 721 226 702 227 733 228 714 229 749 230 727 231 762 232 737 233 775 234 754 235 786 236 767 237 799 238 780 239 813 240 791 241 830 242 806 243 845 244 817 245 858 246 834 247 870 248 847 249 883 250 861 251 898 252 874 253 916 254 888 255 929 256 900 257 942 258 920 259 955 260 934 261 970 262 947 263 986 264 962 265 1001 266 975 267 1017 268 988 269 1033 270 1008 271 1046 272 1024 273 1062 274 1038 275 1080 276 1051 277 1097 278 1065 279 1112 280 1082 281 1126 282 1102 283 1141 284 1117 285 1155 286 1131 287 1173 288 1148 289 1192 290 1162 291 1209 292 1180 293 1224 294 1198 295 1240 296 1213 297 1255 298 1229 299 1278 300 1244 301 1296 302 1259 303 1310 304 1279 305 1327 306 1295 307 1342 308 1315 309 1360 310 1333 311 1380 312 1350 313 1399 314 1366 315 1414 316 1387 317 1431 318 1406 319 1448 320 1423 321 1467 322 1439 323 1488 324 1456 325 1507 326 1472 327 1524 328 1495 329 1543 330 1512 331 1561 332 1532 333 1580 334 1547 335 1602 336 1564 337 1620 338 1583 339 1638 340 1607 341 1656 342 1627 343 1676 344 1646 345 1697 346 1663 347 1718 348 1682 349 1738 350 1701 351 1757 352 1723 353 1777 354 1744 355 1794 356 1762 357 1818 358 1780 359 1841 360 1798 361 1860 362 1821 363 1880 364 1844 365 1897 366 1866 367 1917 368 1887 369 1941 370 1906 371 1962 372 1925 373 1982 374 1947 375 2003 376 1969 377 2023 378 1992 379 2045 380 2012 381 2071 382 2030 383 2094 384 2051 385 2114 386 2075 387 2135 388 2098 389 2155 390 2120 391 2178 392 2141 393 2202 394 2161 395 2225 396 2181 397 2248 398 2209 399 2269 400 2235 401 2287 402 2257 403 2314 404 2276 405 2337 406 2298 407 2361 408 2319 409 2384 410 2346 411 2407 412 2368 413 2426 414 2392 415 2453 416 2411 417 2478 418 2434 419 2502 420 2459 421 2528 422 2487 423 2549 424 2512 425 2570 426 2535 427 2600 428 2557 429 2623 430 2580 431 2647 432 2604 433 2671 434 2632 435 2695 436 2655 437 2718 438 2680 439 2749 440 2701 441 2773 442 2724 443 2799 444 2752 445 2821 446 2780 447 2845 448 2805 449 2869 450 2830 451 2900 452 2855 453 2924 454 2878 455 2950 456 2907 457 2975 458 2934 459 2998 460 2959 461 3026 462 2983 463 3055 464 3007 465 3082 466 3032 467 3109 468 3063 469 3134 470 3090 471 3161 472 3113 473 3189 474 3141 475 3216 476 3166 477 3245 478 3193 479 3271 480 3223 481 3294 482 3252 483 3319 484 3277 485 3350 486 3306 487 3379 488 3330 489 3408 490 3360 491 3434 492 3389 493 3460 494 3416 495 3486 496 3444 497 3520 498 3471 499 3548 500 3496 501 3577 502 3527 503 3602 504 3556 505 3628 506 3588 507 3658 508 3614 509 3692 510 3642 511 3720 512 3668 513 3749 514 3701 515 3776 516 3730 517 3807 518 3758 519 3836 520 3785 521 3868 522 3814 523 3900 524 3839 525 3929 526 3875 527 3958 528 3904 529 3985 530 3935 531 4017 532 3965 533 4047 534 3993 535 4078 536 4023 537 4108 538 4058 539 4137 540 4087 541 4165 542 4117 543 4196 544 4148 545 4231 546 4176 547 4263 548 4207 549 4292 550 4243 551 4323 552 4271 553 4353 554 4302 555 4388 556 4333 557 4422 558 4364 559 4450 560 4397 561 4483 562 4430 563 4512 564 4461 565 4542 566 4495 567 4579 568 4526 569 4611 570 4552 571 4641 572 4589 573 4672 574 4621 575 4707 576 4655 577 4739 578 4686 579 4777 580 4719 581 4810 582 4747 583 4842 584 4783 585 4875 586 4820 587 4905 588 4853 589 4937 590 4884 591 4975 592 4916 593 5007 594 4947 595 5041 596 4986 597 5073 598 5020 599 5106 600 5052 601 5143 602 5086 603 5182 604 5117 605 5217 606 5149 607 5250 608 5188 609 5282 610 5222 611 5314 612 5255 613 5351 614 5289 615 5391 616 5326 617 5424 618 5361 619 5456 620 5399 621 5489 622 5434 623 5521 624 5468 625 5562 626 5505 627 5598 628 5537 629 5635 630 5571 631 5670 632 5611 633 5702 634 5647 635 5738 636 5680 637 5779 638 5714 639 5818 640 5748 641 5851 642 5787 643 5887 644 5825 645 5920 646 5863 647 5956 648 5899 649 5997 650 5933 651 6038 652 5968 653 6071 654 6010 655 6110 656 6050 657 6145 658 6084 659 6184 660 6117 661 6223 662 6155 663 6261 664 6191 665 6300 666 6233 667 6335 668 6271 669 6369 670 6313 671 6410 672 6344 673 6448 674 6383 675 6488 676 6420 677 6524 678 6464 679 6559 680 6501 681 6594 682 6539 683 6640 684 6576 685 6681 686 6615 687 6722 688 6653 689 6760 690 6693 691 6797 692 6732 693 6834 694 6771 695 6881 696 6808 697 6920 698 6845 699 6958 700 6887 701 6993 702 6929 703 7032 704 6971 705 7075 706 7011 707 7118 708 7049 709 7156 710 7087 711 7198 712 7127 713 7237 714 7173 715 7275 716 7211 717 7317 718 7249 719 7364 720 7285 721 7401 722 7326 723 7443 724 7371 725 7484 726 7417 727 7522 728 7456 729 7566 730 7497 731 7609 732 7535 733 7651 734 7574 735 7692 736 7623 737 7730 738 7665 739 7770 740 7703 741 7819 742 7744 743 7861 744 7784 745 7905 746 7823 747 7946 748 7871 749 7985 750 7913 751 8023 752 7953 753 8072 754 7999 755 8116 756 8039 757 8161 758 8083 759 8202 760 8132 761 8241 762 8175 763 8282 764 8217 765 8331 766 8260 767 8377 768 8299 769 8416 770 8342 771 8462 772 8388 773 8506 774 8433 775 8546 776 8477 777 8597 778 8516 779 8642 780 8555 781 8684 782 8605 783 8727 784 8656 785 8772 786 8700 787 8813 788 8741 789 8861 790 8786 791 8903 792 8826 793 8953 794 8880 795 8995 796 8924 797 9040 798 8967 799 9083 800 9010 801 9134 802 9052 803 9180 804 9096 805 9225 806 9149 807 9270 808 9193 809 9312 810 9239 811 9358 812 9286 813 9410 814 9328 815 9456 816 9375 817 9504 818 9424 819 9547 820 9471 821 9589 822 9516 823 9644 824 9562 825 9694 826 9604 827 9739 828 9652 829 9783 830 9700 831 9831 832 9746 833 9876 834 9794 835 9927 836 9840 837 9977 838 9884 839 10023 840 9936 841 10066 842 9990 843 10112 844 10038 845 10157 846 10085 847 10212 848 10130 849 10258 850 10175 851 10307 852 10228 853 10356 854 10277 855 10403 856 10325 857 10452 858 10371 859 10503 860 10415 861 10553 862 10461 863 10603 864 10518 865 10651 866 10568 867 10695 868 10618 869 10745 870 10663 871 10799 872 10713 873 10849 874 10761 875 10897 876 10814 877 10943 878 10865 879 10991 880 10913 881 11042 882 10961 883 11103 884 11008 885 11152 886 11059 887 11202 888 11115 889 11247 890 11163 891 11295 892 11214 893 11351 894 11265 895 11405 896 11314 897 11451 898 11363 899 11501 900 11416 901 11548 902 11472 903 11599 904 11522 905 11657 906 11569 907 11711 908 11617 909 11760 910 11671 911 11810 912 11725 913 11864 914 11776 915 11912 916 11825 917 11970 918 11875 919 12022 920 11925 921 12073 922 11984 923 12126 924 12038 925 12173 926 12093 927 12226 928 12142 929 12280 930 12192 931 12337 932 12244 933 12386 934 12303 935 12442 936 12355 937 12491 938 12407 939 12548 940 12456 941 12604 942 12510 943 12660 944 12559 945 12712 946 12618 947 12761 948 12673 949 12813 950 12726 951 12871 952 12776 953 12928 954 12835 955 12983 956 12884 957 13033 958 12944 959 13085 960 12994 961 13137 962 13054 963 13201 964 13102 965 13256 966 13156 967 13312 968 13210 969 13362 970 13270 971 13416 972 13325 973 13472 974 13379 975 13533 976 13433 977 13586 978 13487 979 13641 980 13543 981 13696 982 13604 983 13745 984 13659 985 13800 986 13713 987 13859 988 13765 989 13915 990 13818 991 13978 992 13882 993 14034 994 13942 995 14088 996 13993 997 14147 998 14050 999 14207 1000 14101