0 1 1 4 2 8 3 12 4 13 5 17 6 23 7 28 8 32 9 35 10 37 11 42 12 48 13 52 14 53 15 57 16 62 17 69 18 72 19 74 20 75 21 81 22 87 23 93 24 95 25 95 26 99 27 106 28 112 29 117 30 116 31 117 32 124 33 133 34 136 35 139 36 138 37 141 38 149 39 157 40 159 41 160 42 162 43 166 44 174 45 181 46 180 47 182 48 187 49 193 50 198 51 203 52 202 53 206 54 212 55 217 56 221 57 224 58 226 59 231 60 237 61 241 62 242 63 246 64 251 65 258 66 261 67 263 68 264 69 270 70 276 71 282 72 284 73 284 74 288 75 295 76 301 77 306 78 305 79 306 80 313 81 322 82 325 83 328 84 327 85 330 86 338 87 346 88 348 89 349 90 351 91 355 92 363 93 370 94 369 95 371 96 376 97 382 98 387 99 392 100 391 101 395 102 401 103 406 104 410 105 413 106 415 107 420 108 426 109 430 110 431 111 435 112 440 113 447 114 450 115 452 116 453 117 459 118 465 119 471 120 473 121 473 122 477 123 484 124 490 125 495 126 494 127 495 128 502 129 511 130 514 131 517 132 516 133 519 134 527 135 535 136 537 137 538 138 540 139 544 140 552 141 559 142 558 143 560 144 565 145 571 146 576 147 581 148 580 149 584 150 590 151 595 152 599 153 602 154 604 155 609 156 615 157 619 158 620 159 624 160 629 161 636 162 639 163 641 164 642 165 648 166 654 167 660 168 662 169 662 170 666 171 673 172 679 173 684 174 683 175 684 176 691 177 700 178 703 179 706 180 705 181 708 182 716 183 724 184 726 185 727 186 729 187 733 188 741 189 748 190 747 191 749 192 754 193 760 194 765 195 770 196 769 197 773 198 779 199 784 200 788 201 791 202 793 203 798 204 804 205 808 206 809 207 813 208 818 209 825 210 828 211 830 212 831 213 837 214 843 215 849 216 851 217 851 218 855 219 862 220 868 221 873 222 872 223 873 224 880 225 889 226 892 227 895 228 894 229 897 230 905 231 913 232 915 233 916 234 918 235 922 236 930 237 937 238 936 239 938 240 943 241 949 242 954 243 959 244 958 245 962 246 968 247 973 248 977 249 980 250 982 251 987 252 993 253 997 254 998 255 1002 256 1007 257 1014 258 1017 259 1019 260 1020 261 1026 262 1032 263 1038 264 1040 265 1040 266 1044 267 1051 268 1057 269 1062 270 1061 271 1062 272 1069 273 1078 274 1081 275 1084 276 1083 277 1086 278 1094 279 1102 280 1104 281 1105 282 1107 283 1111 284 1119 285 1126 286 1125 287 1127 288 1132 289 1138 290 1143 291 1148 292 1147 293 1151 294 1157 295 1162 296 1166 297 1169 298 1171 299 1176 300 1182 301 1186 302 1187 303 1191 304 1196 305 1203 306 1206 307 1208 308 1209 309 1215 310 1221 311 1227 312 1229 313 1229 314 1233 315 1240 316 1246 317 1251 318 1250 319 1251 320 1258 321 1267 322 1270 323 1273 324 1272 325 1275 326 1283 327 1291 328 1293 329 1294 330 1296 331 1300 332 1308 333 1315 334 1314 335 1316 336 1321 337 1327 338 1332 339 1337 340 1336 341 1340 342 1346 343 1351 344 1355 345 1358 346 1360 347 1365 348 1371 349 1375 350 1376 351 1380 352 1385 353 1392 354 1395 355 1397 356 1398 357 1404 358 1410 359 1416 360 1418 361 1418 362 1422 363 1429 364 1435 365 1440 366 1439 367 1440 368 1447 369 1456 370 1459 371 1462 372 1461 373 1464 374 1472 375 1480 376 1482 377 1483 378 1485 379 1489 380 1497 381 1504 382 1503 383 1505 384 1510 385 1516 386 1521 387 1526 388 1525 389 1529 390 1535 391 1540 392 1544 393 1547 394 1549 395 1554 396 1560 397 1564 398 1565 399 1569 400 1574 401 1581 402 1584 403 1586 404 1587 405 1593 406 1599 407 1605 408 1607 409 1607 410 1611 411 1618 412 1624 413 1629 414 1628 415 1629 416 1636 417 1645 418 1648 419 1651 420 1650 421 1653 422 1661 423 1669 424 1671 425 1672 426 1674 427 1678 428 1686 429 1693 430 1692 431 1694 432 1699 433 1705 434 1710 435 1715 436 1714 437 1718 438 1724 439 1729 440 1733 441 1736 442 1738 443 1743 444 1749 445 1753 446 1754 447 1758 448 1763 449 1770 450 1773 451 1775 452 1776 453 1782 454 1788 455 1794 456 1796 457 1796 458 1800 459 1807 460 1813 461 1818 462 1817 463 1818 464 1825 465 1834 466 1837 467 1840 468 1839 469 1842 470 1850 471 1858 472 1860 473 1861 474 1863 475 1867 476 1875 477 1882 478 1881 479 1883 480 1888 481 1894 482 1899 483 1904 484 1903 485 1907 486 1913 487 1918 488 1922 489 1925 490 1927 491 1932 492 1938 493 1942 494 1943 495 1947 496 1952 497 1959 498 1962 499 1964 500 1965 501 1971 502 1977 503 1983 504 1985 505 1985 506 1989 507 1996 508 2002 509 2007 510 2006 511 2007 512 2014 513 2023 514 2026 515 2029 516 2028 517 2031 518 2039 519 2047 520 2049 521 2050 522 2052 523 2056 524 2064 525 2071 526 2070 527 2072 528 2077 529 2083 530 2088 531 2093 532 2092 533 2096 534 2102 535 2107 536 2111 537 2114 538 2116 539 2121 540 2127 541 2131 542 2132 543 2136 544 2141 545 2148 546 2151 547 2153 548 2154 549 2160 550 2166 551 2172 552 2174 553 2174 554 2178 555 2185 556 2191 557 2196 558 2195 559 2196 560 2203 561 2212 562 2215 563 2218 564 2217 565 2220 566 2228 567 2236 568 2238 569 2239 570 2241 571 2245 572 2253 573 2260 574 2259 575 2261 576 2266 577 2272 578 2277 579 2282 580 2281 581 2285 582 2291 583 2296 584 2300 585 2303 586 2305 587 2310 588 2316 589 2320 590 2321 591 2325 592 2330 593 2337 594 2340 595 2342 596 2343 597 2349 598 2355 599 2361 600 2363 601 2363 602 2367 603 2374 604 2380 605 2385 606 2384 607 2385 608 2392 609 2401 610 2404 611 2407 612 2406 613 2409 614 2417 615 2425 616 2427 617 2428 618 2430 619 2434 620 2442 621 2449 622 2448 623 2450 624 2455 625 2461 626 2466 627 2471 628 2470 629 2474 630 2480 631 2485 632 2489 633 2492 634 2494 635 2499 636 2505 637 2509 638 2510 639 2514 640 2519 641 2526 642 2529 643 2531 644 2532 645 2538 646 2544 647 2550 648 2552 649 2552 650 2556 651 2563 652 2569 653 2574 654 2573 655 2574 656 2581 657 2590 658 2593 659 2596 660 2595 661 2598 662 2606 663 2614 664 2616 665 2617 666 2619 667 2623 668 2631 669 2638 670 2637 671 2639 672 2644 673 2650 674 2655 675 2660 676 2659 677 2663 678 2669 679 2674 680 2678 681 2681 682 2683 683 2688 684 2694 685 2698 686 2699 687 2703 688 2708 689 2715 690 2718 691 2720 692 2721 693 2727 694 2733 695 2739 696 2741 697 2741 698 2745 699 2752 700 2758 701 2763 702 2762 703 2763 704 2770 705 2779 706 2782 707 2785 708 2784 709 2787 710 2795 711 2803 712 2805 713 2806 714 2808 715 2812 716 2820 717 2827 718 2826 719 2828 720 2833 721 2839 722 2844 723 2849 724 2848 725 2852 726 2858 727 2863 728 2867 729 2870 730 2872 731 2877 732 2883 733 2887 734 2888 735 2892 736 2897 737 2904 738 2907 739 2909 740 2910 741 2916 742 2922 743 2928 744 2930 745 2930 746 2934 747 2941 748 2947 749 2952 750 2951 751 2952 752 2959 753 2968 754 2971 755 2974 756 2973 757 2976 758 2984 759 2992 760 2994 761 2995 762 2997 763 3001 764 3009 765 3016 766 3015 767 3017 768 3022 769 3028 770 3033 771 3038 772 3037 773 3041 774 3047 775 3052 776 3056 777 3059 778 3061 779 3066 780 3072 781 3076 782 3077 783 3081 784 3086 785 3093 786 3096 787 3098 788 3099 789 3105 790 3111 791 3117 792 3119 793 3119 794 3123 795 3130 796 3136 797 3141 798 3140 799 3141 800 3148 801 3157 802 3160 803 3163 804 3162 805 3165 806 3173 807 3181 808 3183 809 3184 810 3186 811 3190 812 3198 813 3205 814 3204 815 3206 816 3211 817 3217 818 3222 819 3227 820 3226 821 3230 822 3236 823 3241 824 3245 825 3248 826 3250 827 3255 828 3261 829 3265 830 3266 831 3270 832 3275 833 3282 834 3285 835 3287 836 3288 837 3294 838 3300 839 3306 840 3308 841 3308 842 3312 843 3319 844 3325 845 3330 846 3329 847 3330 848 3337 849 3346 850 3349 851 3352 852 3351 853 3354 854 3362 855 3370 856 3372 857 3373 858 3375 859 3379 860 3387 861 3394 862 3393 863 3395 864 3400 865 3406 866 3411 867 3416 868 3415 869 3419 870 3425 871 3430 872 3434 873 3437 874 3439 875 3444 876 3450 877 3454 878 3455 879 3459 880 3464 881 3471 882 3474 883 3476 884 3477 885 3483 886 3489 887 3495 888 3497 889 3497 890 3501 891 3508 892 3514 893 3519 894 3518 895 3519 896 3526 897 3535 898 3538 899 3541 900 3540 901 3543 902 3551 903 3559 904 3561 905 3562 906 3564 907 3568 908 3576 909 3583 910 3582 911 3584 912 3589 913 3595 914 3600 915 3605 916 3604 917 3608 918 3614 919 3619 920 3623 921 3626 922 3628 923 3633 924 3639 925 3643 926 3644 927 3648 928 3653 929 3660 930 3663 931 3665 932 3666 933 3672 934 3678 935 3684 936 3686 937 3686 938 3690 939 3697 940 3703 941 3708 942 3707 943 3708 944 3715 945 3724 946 3727 947 3730 948 3729 949 3732 950 3740 951 3748 952 3750 953 3751 954 3753 955 3757 956 3765 957 3772 958 3771 959 3773 960 3778 961 3784 962 3789 963 3794 964 3793 965 3797 966 3803 967 3808 968 3812 969 3815 970 3817 971 3822 972 3828 973 3832 974 3833 975 3837 976 3842 977 3849 978 3852 979 3854 980 3855 981 3861 982 3867 983 3873 984 3875 985 3875 986 3879 987 3886 988 3892 989 3897 990 3896 991 3897 992 3904 993 3913 994 3916 995 3919 996 3918 997 3921 998 3929 999 3937 1000 3939