0 1 1 5 2 8 3 8 4 11 5 17 6 25 7 27 8 24 9 30 10 38 11 46 12 47 13 44 14 46 15 50 16 64 17 68 18 65 19 66 20 70 21 80 22 80 23 83 24 87 25 91 26 100 27 100 28 99 29 99 30 109 31 121 32 121 33 119 34 119 35 125 36 133 37 139 38 140 39 140 40 145 41 153 42 155 43 152 44 158 45 166 46 174 47 175 48 172 49 174 50 178 51 192 52 196 53 193 54 194 55 198 56 208 57 208 58 211 59 215 60 219 61 228 62 228 63 227 64 227 65 237 66 249 67 249 68 247 69 247 70 253 71 261 72 267 73 268 74 268 75 273 76 281 77 283 78 280 79 286 80 294 81 302 82 303 83 300 84 302 85 306 86 320 87 324 88 321 89 322 90 326 91 336 92 336 93 339 94 343 95 347 96 356 97 356 98 355 99 355 100 365 101 377 102 377 103 375 104 375 105 381 106 389 107 395 108 396 109 396 110 401 111 409 112 411 113 408 114 414 115 422 116 430 117 431 118 428 119 430 120 434 121 448 122 452 123 449 124 450 125 454 126 464 127 464 128 467 129 471 130 475 131 484 132 484 133 483 134 483 135 493 136 505 137 505 138 503 139 503 140 509 141 517 142 523 143 524 144 524 145 529 146 537 147 539 148 536 149 542 150 550 151 558 152 559 153 556 154 558 155 562 156 576 157 580 158 577 159 578 160 582 161 592 162 592 163 595 164 599 165 603 166 612 167 612 168 611 169 611 170 621 171 633 172 633 173 631 174 631 175 637 176 645 177 651 178 652 179 652 180 657 181 665 182 667 183 664 184 670 185 678 186 686 187 687 188 684 189 686 190 690 191 704 192 708 193 705 194 706 195 710 196 720 197 720 198 723 199 727 200 731 201 740 202 740 203 739 204 739 205 749 206 761 207 761 208 759 209 759 210 765 211 773 212 779 213 780 214 780 215 785 216 793 217 795 218 792 219 798 220 806 221 814 222 815 223 812 224 814 225 818 226 832 227 836 228 833 229 834 230 838 231 848 232 848 233 851 234 855 235 859 236 868 237 868 238 867 239 867 240 877 241 889 242 889 243 887 244 887 245 893 246 901 247 907 248 908 249 908 250 913 251 921 252 923 253 920 254 926 255 934 256 942 257 943 258 940 259 942 260 946 261 960 262 964 263 961 264 962 265 966 266 976 267 976 268 979 269 983 270 987 271 996 272 996 273 995 274 995 275 1005 276 1017 277 1017 278 1015 279 1015 280 1021 281 1029 282 1035 283 1036 284 1036 285 1041 286 1049 287 1051 288 1048 289 1054 290 1062 291 1070 292 1071 293 1068 294 1070 295 1074 296 1088 297 1092 298 1089 299 1090 300 1094 301 1104 302 1104 303 1107 304 1111 305 1115 306 1124 307 1124 308 1123 309 1123 310 1133 311 1145 312 1145 313 1143 314 1143 315 1149 316 1157 317 1163 318 1164 319 1164 320 1169 321 1177 322 1179 323 1176 324 1182 325 1190 326 1198 327 1199 328 1196 329 1198 330 1202 331 1216 332 1220 333 1217 334 1218 335 1222 336 1232 337 1232 338 1235 339 1239 340 1243 341 1252 342 1252 343 1251 344 1251 345 1261 346 1273 347 1273 348 1271 349 1271 350 1277 351 1285 352 1291 353 1292 354 1292 355 1297 356 1305 357 1307 358 1304 359 1310 360 1318 361 1326 362 1327 363 1324 364 1326 365 1330 366 1344 367 1348 368 1345 369 1346 370 1350 371 1360 372 1360 373 1363 374 1367 375 1371 376 1380 377 1380 378 1379 379 1379 380 1389 381 1401 382 1401 383 1399 384 1399 385 1405 386 1413 387 1419 388 1420 389 1420 390 1425 391 1433 392 1435 393 1432 394 1438 395 1446 396 1454 397 1455 398 1452 399 1454 400 1458 401 1472 402 1476 403 1473 404 1474 405 1478 406 1488 407 1488 408 1491 409 1495 410 1499 411 1508 412 1508 413 1507 414 1507 415 1517 416 1529 417 1529 418 1527 419 1527 420 1533 421 1541 422 1547 423 1548 424 1548 425 1553 426 1561 427 1563 428 1560 429 1566 430 1574 431 1582 432 1583 433 1580 434 1582 435 1586 436 1600 437 1604 438 1601 439 1602 440 1606 441 1616 442 1616 443 1619 444 1623 445 1627 446 1636 447 1636 448 1635 449 1635 450 1645 451 1657 452 1657 453 1655 454 1655 455 1661 456 1669 457 1675 458 1676 459 1676 460 1681 461 1689 462 1691 463 1688 464 1694 465 1702 466 1710 467 1711 468 1708 469 1710 470 1714 471 1728 472 1732 473 1729 474 1730 475 1734 476 1744 477 1744 478 1747 479 1751 480 1755 481 1764 482 1764 483 1763 484 1763 485 1773 486 1785 487 1785 488 1783 489 1783 490 1789 491 1797 492 1803 493 1804 494 1804 495 1809 496 1817 497 1819 498 1816 499 1822 500 1830 501 1838 502 1839 503 1836 504 1838 505 1842 506 1856 507 1860 508 1857 509 1858 510 1862 511 1872 512 1872 513 1875 514 1879 515 1883 516 1892 517 1892 518 1891 519 1891 520 1901 521 1913 522 1913 523 1911 524 1911 525 1917 526 1925 527 1931 528 1932 529 1932 530 1937 531 1945 532 1947 533 1944 534 1950 535 1958 536 1966 537 1967 538 1964 539 1966 540 1970 541 1984 542 1988 543 1985 544 1986 545 1990 546 2000 547 2000 548 2003 549 2007 550 2011 551 2020 552 2020 553 2019 554 2019 555 2029 556 2041 557 2041 558 2039 559 2039 560 2045 561 2053 562 2059 563 2060 564 2060 565 2065 566 2073 567 2075 568 2072 569 2078 570 2086 571 2094 572 2095 573 2092 574 2094 575 2098 576 2112 577 2116 578 2113 579 2114 580 2118 581 2128 582 2128 583 2131 584 2135 585 2139 586 2148 587 2148 588 2147 589 2147 590 2157 591 2169 592 2169 593 2167 594 2167 595 2173 596 2181 597 2187 598 2188 599 2188 600 2193 601 2201 602 2203 603 2200 604 2206 605 2214 606 2222 607 2223 608 2220 609 2222 610 2226 611 2240 612 2244 613 2241 614 2242 615 2246 616 2256 617 2256 618 2259 619 2263 620 2267 621 2276 622 2276 623 2275 624 2275 625 2285 626 2297 627 2297 628 2295 629 2295 630 2301 631 2309 632 2315 633 2316 634 2316 635 2321 636 2329 637 2331 638 2328 639 2334 640 2342 641 2350 642 2351 643 2348 644 2350 645 2354 646 2368 647 2372 648 2369 649 2370 650 2374 651 2384 652 2384 653 2387 654 2391 655 2395 656 2404 657 2404 658 2403 659 2403 660 2413 661 2425 662 2425 663 2423 664 2423 665 2429 666 2437 667 2443 668 2444 669 2444 670 2449 671 2457 672 2459 673 2456 674 2462 675 2470 676 2478 677 2479 678 2476 679 2478 680 2482 681 2496 682 2500 683 2497 684 2498 685 2502 686 2512 687 2512 688 2515 689 2519 690 2523 691 2532 692 2532 693 2531 694 2531 695 2541 696 2553 697 2553 698 2551 699 2551 700 2557 701 2565 702 2571 703 2572 704 2572 705 2577 706 2585 707 2587 708 2584 709 2590 710 2598 711 2606 712 2607 713 2604 714 2606 715 2610 716 2624 717 2628 718 2625 719 2626 720 2630 721 2640 722 2640 723 2643 724 2647 725 2651 726 2660 727 2660 728 2659 729 2659 730 2669 731 2681 732 2681 733 2679 734 2679 735 2685 736 2693 737 2699 738 2700 739 2700 740 2705 741 2713 742 2715 743 2712 744 2718 745 2726 746 2734 747 2735 748 2732 749 2734 750 2738 751 2752 752 2756 753 2753 754 2754 755 2758 756 2768 757 2768 758 2771 759 2775 760 2779 761 2788 762 2788 763 2787 764 2787 765 2797 766 2809 767 2809 768 2807 769 2807 770 2813 771 2821 772 2827 773 2828 774 2828 775 2833 776 2841 777 2843 778 2840 779 2846 780 2854 781 2862 782 2863 783 2860 784 2862 785 2866 786 2880 787 2884 788 2881 789 2882 790 2886 791 2896 792 2896 793 2899 794 2903 795 2907 796 2916 797 2916 798 2915 799 2915 800 2925 801 2937 802 2937 803 2935 804 2935 805 2941 806 2949 807 2955 808 2956 809 2956 810 2961 811 2969 812 2971 813 2968 814 2974 815 2982 816 2990 817 2991 818 2988 819 2990 820 2994 821 3008 822 3012 823 3009 824 3010 825 3014 826 3024 827 3024 828 3027 829 3031 830 3035 831 3044 832 3044 833 3043 834 3043 835 3053 836 3065 837 3065 838 3063 839 3063 840 3069 841 3077 842 3083 843 3084 844 3084 845 3089 846 3097 847 3099 848 3096 849 3102 850 3110 851 3118 852 3119 853 3116 854 3118 855 3122 856 3136 857 3140 858 3137 859 3138 860 3142 861 3152 862 3152 863 3155 864 3159 865 3163 866 3172 867 3172 868 3171 869 3171 870 3181 871 3193 872 3193 873 3191 874 3191 875 3197 876 3205 877 3211 878 3212 879 3212 880 3217 881 3225 882 3227 883 3224 884 3230 885 3238 886 3246 887 3247 888 3244 889 3246 890 3250 891 3264 892 3268 893 3265 894 3266 895 3270 896 3280 897 3280 898 3283 899 3287 900 3291 901 3300 902 3300 903 3299 904 3299 905 3309 906 3321 907 3321 908 3319 909 3319 910 3325 911 3333 912 3339 913 3340 914 3340 915 3345 916 3353 917 3355 918 3352 919 3358 920 3366 921 3374 922 3375 923 3372 924 3374 925 3378 926 3392 927 3396 928 3393 929 3394 930 3398 931 3408 932 3408 933 3411 934 3415 935 3419 936 3428 937 3428 938 3427 939 3427 940 3437 941 3449 942 3449 943 3447 944 3447 945 3453 946 3461 947 3467 948 3468 949 3468 950 3473 951 3481 952 3483 953 3480 954 3486 955 3494 956 3502 957 3503 958 3500 959 3502 960 3506 961 3520 962 3524 963 3521 964 3522 965 3526 966 3536 967 3536 968 3539 969 3543 970 3547 971 3556 972 3556 973 3555 974 3555 975 3565 976 3577 977 3577 978 3575 979 3575 980 3581 981 3589 982 3595 983 3596 984 3596 985 3601 986 3609 987 3611 988 3608 989 3614 990 3622 991 3630 992 3631 993 3628 994 3630 995 3634 996 3648 997 3652 998 3649 999 3650 1000 3654