1 0 2 1 3 2 4 4 5 6 6 8 7 9 8 12 9 14 10 17 11 21 12 23 13 25 14 29 15 29 16 33 17 37 18 41 19 42 20 46 21 49 22 51 23 52 24 56 25 62 26 64 27 68 28 66 29 70 30 74 31 83 32 86 33 86 34 90 35 93 36 99 37 103 38 108 39 106 40 111 41 113 42 119 43 123 44 125 45 124 46 130 47 139 48 147 49 144 50 148 51 148 52 156 53 160 54 163 55 164 56 168 57 174 58 182 59 180 60 182 61 186 62 190 63 200 64 206 65 210 66 204 67 217 68 219 69 224 70 228 71 230 72 230 73 239 74 243 75 249 76 253 77 249 78 262 79 261 80 263 81 273 82 281 83 279 84 283 85 285 86 286 87 290 88 297 89 297 90 305 91 303 92 311 93 316 94 322 95 322 96 326 97 332 98 341 99 347 100 352 101 360 102 362 103 366 104 364 105 372 106 377 107 376 108 384 109 390 110 396 111 398 112 402 113 402 114 406 115 413 116 415 117 419 118 421 119 426 120 430 121 438 122 440 123 435 124 443 125 457 126 457 127 463 128 467 129 476 130 481 131 479 132 481 133 491 134 501 135 501 136 497 137 505 138 512 139 516 140 523 141 533 142 535 143 539 144 535 145 541 146 543 147 558 148 554 149 562 150 562 151 570 152 574 153 583 154 583 155 588 156 594 157 600 158 606 159 612 160 618 161 612 162 622 163 633 164 634 165 632 166 638 167 652 168 658 169 656 170 662 171 662 172 670 173 671 174 675 175 675 176 679 177 691 178 694 179 700 180 704 181 706 182 705 183 713 184 711 185 723 186 721 187 729 188 741 189 735 190 757 191 760 192 753 193 769 194 771 195 769 196 783 197 785 198 795 199 789 200 797 201 798 202 806 203 806 204 812 205 823 206 831 207 837 208 835 209 833 210 841 211 844 212 852 213 860 214 854 215 858 216 866 217 864 218 891 219 885 220 896 221 898 222 910 223 920 224 930 225 926 226 934 227 938 228 938 229 943 230 941 231 947 232 952 233 964 234 968 235 976 236 968 237 972 238 972 239 978 240 986 241 991 242 1005 243 1007 244 1005 245 1007 246 1015 247 1033 248 1038 249 1028 250 1030 251 1040 252 1041 253 1045 254 1049 255 1057 256 1049 257 1059 258 1061 259 1065 260 1085 261 1087 262 1085 263 1089 264 1105 265 1107 266 1111 267 1111 268 1125 269 1133 270 1127 271 1141 272 1145 273 1153 274 1145 275 1154 276 1168 277 1160 278 1164 279 1181 280 1189 281 1193 282 1195 283 1199 284 1216 285 1218 286 1222 287 1228 288 1226 289 1230 290 1222 291 1246 292 1248 293 1248 294 1257 295 1265 296 1270 297 1282 298 1282 299 1292 300 1306 301 1306 302 1296 303 1304 304 1310 305 1318 306 1318 307 1313 308 1319 309 1323 310 1346 311 1350 312 1348 313 1354 314 1358 315 1358 316 1364 317 1364 318 1382 319 1386 320 1385 321 1393 322 1393 323 1393 324 1405 325 1401 326 1417 327 1426 328 1442 329 1432 330 1441 331 1455 332 1455 333 1459 334 1461 335 1475 336 1479 337 1489 338 1493 339 1489 340 1497 341 1501 342 1495 343 1496 344 1512 345 1519 346 1521 347 1533 348 1533 349 1533 350 1539 351 1553 352 1553 353 1559 354 1563 355 1555 356 1561 357 1571 358 1570 359 1566 360 1578 361 1592 362 1596 363 1602 364 1601 365 1611 366 1621 367 1609 368 1634 369 1650 370 1654 371 1658 372 1656 373 1664 374 1676 375 1676 376 1686 377 1692 378 1697 379 1698 380 1708 381 1714 382 1720 383 1728 384 1732 385 1736 386 1746 387 1754 388 1750 389 1756 390 1758 391 1762 392 1758 393 1752 394 1769 395 1765 396 1769 397 1771 398 1775 399 1791 400 1792 401 1792 402 1796 403 1808 404 1812 405 1820 406 1832 407 1826 408 1830 409 1834 410 1841 411 1851 412 1839 413 1853 414 1861 415 1869 416 1877 417 1873 418 1887 419 1886 420 1902 421 1896 422 1909 423 1905 424 1913 425 1929 426 1929 427 1931 428 1937 429 1953 430 1959 431 1967 432 1965 433 1967 434 1967 435 1984 436 1992 437 1991 438 2001 439 2009 440 2009 441 2015 442 2011 443 2033 444 2035 445 2043 446 2042 447 2064 448 2064 449 2070 450 2078 451 2080 452 2088 453 2093 454 2101 455 2099 456 2103 457 2105 458 2122 459 2126 460 2118 461 2124 462 2134 463 2150 464 2162 465 2172 466 2176 467 2172 468 2172 469 2168 470 2180 471 2176 472 2178 473 2192 474 2200 475 2208 476 2212 477 2212 478 2220 479 2222 480 2230 481 2248 482 2250 483 2262 484 2272 485 2276 486 2258 487 2264 488 2273 489 2283 490 2301 491 2303 492 2295 493 2304 494 2304 495 2308 496 2316 497 2328 498 2318 499 2322 500 2342 501 2338 502 2344 503 2340 504 2351 505 2363 506 2363 507 2365 508 2371 509 2375 510 2387 511 2391 512 2401 513 2409 514 2399 515 2411 516 2421 517 2424 518 2420 519 2426 520 2441 521 2439 522 2439 523 2445 524 2455 525 2459 526 2467 527 2487 528 2481 529 2487 530 2491 531 2503 532 2499 533 2506 534 2520 535 2526 536 2514 537 2535 538 2539 539 2535 540 2557 541 2565 542 2557 543 2561 544 2569 545 2563 546 2571 547 2575 548 2575 549 2597 550 2598 551 2610 552 2618 553 2618 554 2622 555 2624 556 2632 557 2628 558 2642 559 2657 560 2659 561 2663 562 2665 563 2671 564 2679 565 2664 566 2684 567 2686 568 2690 569 2690 570 2696 571 2716 572 2716 573 2732 574 2730 575 2744 576 2744 577 2756 578 2764 579 2759 580 2771 581 2766 582 2774 583 2780 584 2774 585 2782 586 2792 587 2796 588 2788 589 2800 590 2816 591 2832 592 2826 593 2832 594 2830 595 2847 596 2851 597 2855 598 2861 599 2867 600 2869 601 2894 602 2902 603 2900 604 2910 605 2916 606 2910 607 2914 608 2922 609 2930 610 2929 611 2939 612 2949 613 2941 614 2947 615 2953 616 2963 617 2967 618 2987 619 2981 620 2991 621 3003 622 3009 623 3017 624 3022 625 3023 626 3027 627 3021 628 3033 629 3045 630 3035 631 3051 632 3047 633 3049 634 3067 635 3077 636 3089 637 3093 638 3079 639 3087 640 3101 641 3111 642 3122 643 3114 644 3126 645 3130 646 3128 647 3134 648 3143 649 3141 650 3167 651 3177 652 3183 653 3181 654 3191 655 3204 656 3202 657 3216 658 3224 659 3230 660 3220 661 3226 662 3236 663 3240 664 3238 665 3246 666 3256 667 3262 668 3266 669 3268 670 3275 671 3269 672 3277 673 3283 674 3293 675 3283 676 3290 677 3298 678 3312 679 3316 680 3318 681 3334 682 3346 683 3346 684 3354 685 3342 686 3352 687 3366 688 3380 689 3390 690 3384 691 3375 692 3389 693 3406 694 3414 695 3410 696 3414 697 3418 698 3446 699 3440 700 3450 701 3458 702 3460 703 3462 704 3468 705 3474 706 3483 707 3499 708 3507 709 3501 710 3509 711 3521 712 3523 713 3541 714 3550 715 3544 716 3556 717 3548 718 3562 719 3558 720 3562 721 3554 722 3570 723 3575 724 3583 725 3575 726 3585 727 3593 728 3591 729 3609 730 3617 731 3613 732 3617 733 3631 734 3639 735 3637 736 3641 737 3647 738 3659 739 3678 740 3677 741 3685 742 3685 743 3687 744 3693 745 3687 746 3695 747 3693 748 3713 749 3717 750 3717 751 3733 752 3735 753 3735 754 3735 755 3745 756 3757 757 3761 758 3768 759 3774 760 3780 761 3790 762 3782 763 3790 764 3802 765 3806 766 3815 767 3813 768 3817 769 3835 770 3845 771 3839 772 3829 773 3835 774 3837 775 3849 776 3849 777 3855 778 3871 779 3865 780 3876 781 3896 782 3912 783 3900 784 3926 785 3930 786 3938 787 3952 788 3954 789 3944 790 3961 791 3965 792 3969 793 3963 794 3972 795 3988 796 3984 797 3984 798 4006 799 3996 800 4004 801 4012 802 4022 803 4042 804 4034 805 4042 806 4046 807 4046 808 4066 809 4068 810 4070 811 4074 812 4075 813 4075 814 4087 815 4093 816 4109 817 4104 818 4100 819 4110 820 4128 821 4124 822 4130 823 4138 824 4132 825 4140 826 4150 827 4148 828 4152 829 4160 830 4154 831 4168 832 4160 833 4174 834 4192 835 4185 836 4205 837 4203 838 4215 839 4231 840 4233 841 4235 842 4243 843 4264 844 4260 845 4270 846 4272 847 4284 848 4279 849 4279 850 4291 851 4293 852 4299 853 4311 854 4321 855 4315 856 4337 857 4351 858 4347 859 4359 860 4363 861 4369 862 4369 863 4377 864 4373 865 4377 866 4379 867 4387 868 4401 869 4405 870 4417 871 4429 872 4425 873 4433 874 4431 875 4435 876 4443 877 4473 878 4455 879 4459 880 4453 881 4469 882 4473 883 4489 884 4491 885 4499 886 4505 887 4498 888 4510 889 4508 890 4514 891 4534 892 4540 893 4550 894 4558 895 4561 896 4567 897 4563 898 4565 899 4571 900 4571 901 4579 902 4573 903 4581 904 4593 905 4595 906 4601 907 4610 908 4614 909 4626 910 4638 911 4636 912 4646 913 4642 914 4652 915 4688 916 4686 917 4684 918 4700 919 4696 920 4709 921 4713 922 4717 923 4713 924 4712 925 4726 926 4738 927 4720 928 4734 929 4760 930 4760 931 4766 932 4778 933 4784 934 4794 935 4802 936 4800 937 4818 938 4820 939 4828 940 4845 941 4851 942 4843 943 4870 944 4868 945 4876 946 4884 947 4888 948 4894 949 4900 950 4894 951 4908 952 4906 953 4912 954 4914 955 4914 956 4918 957 4928 958 4936 959 4934 960 4950 961 4955 962 4951 963 4949 964 4947 965 4963 966 4971 967 4959 968 4981 969 4989 970 4989 971 4997 972 5007 973 5017 974 5023 975 5031 976 5032 977 5022 978 5030 979 5042 980 5058 981 5052 982 5058 983 5065 984 5057 985 5063 986 5089 987 5089 988 5103 989 5105 990 5115 991 5127 992 5131 993 5149 994 5153 995 5139 996 5147 997 5149 998 5163 999 5161 1000 5161