0 0 1 1 2 3 3 6 4 10 5 15 6 21 7 28 8 28 9 29 10 31 11 34 12 38 13 43 14 49 15 56 16 56 17 57 18 59 19 62 20 66 21 71 22 77 23 84 24 84 25 85 26 87 27 90 28 94 29 99 30 105 31 112 32 112 33 113 34 115 35 118 36 122 37 127 38 133 39 140 40 140 41 141 42 143 43 146 44 150 45 155 46 161 47 168 48 168 49 169 50 171 51 174 52 178 53 183 54 189 55 196 56 196 57 197 58 199 59 202 60 206 61 211 62 217 63 224 64 224 65 225 66 227 67 230 68 234 69 239 70 245 71 252 72 252 73 253 74 255 75 258 76 262 77 267 78 273 79 280 80 280 81 281 82 283 83 286 84 290 85 295 86 301 87 308 88 308 89 309 90 311 91 314 92 318 93 323 94 329 95 336 96 336 97 337 98 339 99 342 100 346 101 351 102 357 103 364 104 364 105 365 106 367 107 370 108 374 109 379 110 385 111 392 112 392 113 393 114 395 115 398 116 402 117 407 118 413 119 420 120 420 121 421 122 423 123 426 124 430 125 435 126 441 127 448 128 448 129 449 130 451 131 454 132 458 133 463 134 469 135 476 136 476 137 477 138 479 139 482 140 486 141 491 142 497 143 504 144 504 145 505 146 507 147 510 148 514 149 519 150 525 151 532 152 532 153 533 154 535 155 538 156 542 157 547 158 553 159 560 160 560 161 561 162 563 163 566 164 570 165 575 166 581 167 588 168 588 169 589 170 591 171 594 172 598 173 603 174 609 175 616 176 616 177 617 178 619 179 622 180 626 181 631 182 637 183 644 184 644 185 645 186 647 187 650 188 654 189 659 190 665 191 672 192 672 193 673 194 675 195 678 196 682 197 687 198 693 199 700 200 700 201 701 202 703 203 706 204 710 205 715 206 721 207 728 208 728 209 729 210 731 211 734 212 738 213 743 214 749 215 756 216 756 217 757 218 759 219 762 220 766 221 771 222 777 223 784 224 784 225 785 226 787 227 790 228 794 229 799 230 805 231 812 232 812 233 813 234 815 235 818 236 822 237 827 238 833 239 840 240 840 241 841 242 843 243 846 244 850 245 855 246 861 247 868 248 868 249 869 250 871 251 874 252 878 253 883 254 889 255 896 256 896 257 897 258 899 259 902 260 906 261 911 262 917 263 924 264 924 265 925 266 927 267 930 268 934 269 939 270 945 271 952 272 952 273 953 274 955 275 958 276 962 277 967 278 973 279 980 280 980 281 981 282 983 283 986 284 990 285 995 286 1001 287 1008 288 1008 289 1009 290 1011 291 1014 292 1018 293 1023 294 1029 295 1036 296 1036 297 1037 298 1039 299 1042 300 1046 301 1051 302 1057 303 1064 304 1064 305 1065 306 1067 307 1070 308 1074 309 1079 310 1085 311 1092 312 1092 313 1093 314 1095 315 1098 316 1102 317 1107 318 1113 319 1120 320 1120 321 1121 322 1123 323 1126 324 1130 325 1135 326 1141 327 1148 328 1148 329 1149 330 1151 331 1154 332 1158 333 1163 334 1169 335 1176 336 1176 337 1177 338 1179 339 1182 340 1186 341 1191 342 1197 343 1204 344 1204 345 1205 346 1207 347 1210 348 1214 349 1219 350 1225 351 1232 352 1232 353 1233 354 1235 355 1238 356 1242 357 1247 358 1253 359 1260 360 1260 361 1261 362 1263 363 1266 364 1270 365 1275 366 1281 367 1288 368 1288 369 1289 370 1291 371 1294 372 1298 373 1303 374 1309 375 1316 376 1316 377 1317 378 1319 379 1322 380 1326 381 1331 382 1337 383 1344 384 1344 385 1345 386 1347 387 1350 388 1354 389 1359 390 1365 391 1372 392 1372 393 1373 394 1375 395 1378 396 1382 397 1387 398 1393 399 1400 400 1400 401 1401 402 1403 403 1406 404 1410 405 1415 406 1421 407 1428 408 1428 409 1429 410 1431 411 1434 412 1438 413 1443 414 1449 415 1456 416 1456 417 1457 418 1459 419 1462 420 1466 421 1471 422 1477 423 1484 424 1484 425 1485 426 1487 427 1490 428 1494 429 1499 430 1505 431 1512 432 1512 433 1513 434 1515 435 1518 436 1522 437 1527 438 1533 439 1540 440 1540 441 1541 442 1543 443 1546 444 1550 445 1555 446 1561 447 1568 448 1568 449 1569 450 1571 451 1574 452 1578 453 1583 454 1589 455 1596 456 1596 457 1597 458 1599 459 1602 460 1606 461 1611 462 1617 463 1624 464 1624 465 1625 466 1627 467 1630 468 1634 469 1639 470 1645 471 1652 472 1652 473 1653 474 1655 475 1658 476 1662 477 1667 478 1673 479 1680 480 1680 481 1681 482 1683 483 1686 484 1690 485 1695 486 1701 487 1708 488 1708 489 1709 490 1711 491 1714 492 1718 493 1723 494 1729 495 1736 496 1736 497 1737 498 1739 499 1742 500 1746 501 1751 502 1757 503 1764 504 1764 505 1765 506 1767 507 1770 508 1774 509 1779 510 1785 511 1792 512 1792 513 1793 514 1795 515 1798 516 1802 517 1807 518 1813 519 1820 520 1820 521 1821 522 1823 523 1826 524 1830 525 1835 526 1841 527 1848 528 1848 529 1849 530 1851 531 1854 532 1858 533 1863 534 1869 535 1876 536 1876 537 1877 538 1879 539 1882 540 1886 541 1891 542 1897 543 1904 544 1904 545 1905 546 1907 547 1910 548 1914 549 1919 550 1925 551 1932 552 1932 553 1933 554 1935 555 1938 556 1942 557 1947 558 1953 559 1960 560 1960 561 1961 562 1963 563 1966 564 1970 565 1975 566 1981 567 1988 568 1988 569 1989 570 1991 571 1994 572 1998 573 2003 574 2009 575 2016 576 2016 577 2017 578 2019 579 2022 580 2026 581 2031 582 2037 583 2044 584 2044 585 2045 586 2047 587 2050 588 2054 589 2059 590 2065 591 2072 592 2072 593 2073 594 2075 595 2078 596 2082 597 2087 598 2093 599 2100 600 2100 601 2101 602 2103 603 2106 604 2110 605 2115 606 2121 607 2128 608 2128 609 2129 610 2131 611 2134 612 2138 613 2143 614 2149 615 2156 616 2156 617 2157 618 2159 619 2162 620 2166 621 2171 622 2177 623 2184 624 2184 625 2185 626 2187 627 2190 628 2194 629 2199 630 2205 631 2212 632 2212 633 2213 634 2215 635 2218 636 2222 637 2227 638 2233 639 2240 640 2240 641 2241 642 2243 643 2246 644 2250 645 2255 646 2261 647 2268 648 2268 649 2269 650 2271 651 2274 652 2278 653 2283 654 2289 655 2296 656 2296 657 2297 658 2299 659 2302 660 2306 661 2311 662 2317 663 2324 664 2324 665 2325 666 2327 667 2330 668 2334 669 2339 670 2345 671 2352 672 2352 673 2353 674 2355 675 2358 676 2362 677 2367 678 2373 679 2380 680 2380 681 2381 682 2383 683 2386 684 2390 685 2395 686 2401 687 2408 688 2408 689 2409 690 2411 691 2414 692 2418 693 2423 694 2429 695 2436 696 2436 697 2437 698 2439 699 2442 700 2446 701 2451 702 2457 703 2464 704 2464 705 2465 706 2467 707 2470 708 2474 709 2479 710 2485 711 2492 712 2492 713 2493 714 2495 715 2498 716 2502 717 2507 718 2513 719 2520 720 2520 721 2521 722 2523 723 2526 724 2530 725 2535 726 2541 727 2548 728 2548 729 2549 730 2551 731 2554 732 2558 733 2563 734 2569 735 2576 736 2576 737 2577 738 2579 739 2582 740 2586 741 2591 742 2597 743 2604 744 2604 745 2605 746 2607 747 2610 748 2614 749 2619 750 2625 751 2632 752 2632 753 2633 754 2635 755 2638 756 2642 757 2647 758 2653 759 2660 760 2660 761 2661 762 2663 763 2666 764 2670 765 2675 766 2681 767 2688 768 2688 769 2689 770 2691 771 2694 772 2698 773 2703 774 2709 775 2716 776 2716 777 2717 778 2719 779 2722 780 2726 781 2731 782 2737 783 2744 784 2744 785 2745 786 2747 787 2750 788 2754 789 2759 790 2765 791 2772 792 2772 793 2773 794 2775 795 2778 796 2782 797 2787 798 2793 799 2800 800 2800 801 2801 802 2803 803 2806 804 2810 805 2815 806 2821 807 2828 808 2828 809 2829 810 2831 811 2834 812 2838 813 2843 814 2849 815 2856 816 2856 817 2857 818 2859 819 2862 820 2866 821 2871 822 2877 823 2884 824 2884 825 2885 826 2887 827 2890 828 2894 829 2899 830 2905 831 2912 832 2912 833 2913 834 2915 835 2918 836 2922 837 2927 838 2933 839 2940 840 2940 841 2941 842 2943 843 2946 844 2950 845 2955 846 2961 847 2968 848 2968 849 2969 850 2971 851 2974 852 2978 853 2983 854 2989 855 2996 856 2996 857 2997 858 2999 859 3002 860 3006 861 3011 862 3017 863 3024 864 3024 865 3025 866 3027 867 3030 868 3034 869 3039 870 3045 871 3052 872 3052 873 3053 874 3055 875 3058 876 3062 877 3067 878 3073 879 3080 880 3080 881 3081 882 3083 883 3086 884 3090 885 3095 886 3101 887 3108 888 3108 889 3109 890 3111 891 3114 892 3118 893 3123 894 3129 895 3136 896 3136 897 3137 898 3139 899 3142 900 3146 901 3151 902 3157 903 3164 904 3164 905 3165 906 3167 907 3170 908 3174 909 3179 910 3185 911 3192 912 3192 913 3193 914 3195 915 3198 916 3202 917 3207 918 3213 919 3220 920 3220 921 3221 922 3223 923 3226 924 3230 925 3235 926 3241 927 3248 928 3248 929 3249 930 3251 931 3254 932 3258 933 3263 934 3269 935 3276 936 3276 937 3277 938 3279 939 3282 940 3286 941 3291 942 3297 943 3304 944 3304 945 3305 946 3307 947 3310 948 3314 949 3319 950 3325 951 3332 952 3332 953 3333 954 3335 955 3338 956 3342 957 3347 958 3353 959 3360 960 3360 961 3361 962 3363 963 3366 964 3370 965 3375 966 3381 967 3388 968 3388 969 3389 970 3391 971 3394 972 3398 973 3403 974 3409 975 3416 976 3416 977 3417 978 3419 979 3422 980 3426 981 3431 982 3437 983 3444 984 3444 985 3445 986 3447 987 3450 988 3454 989 3459 990 3465 991 3472 992 3472 993 3473 994 3475 995 3478 996 3482 997 3487 998 3493 999 3500 1000 3500