1 0 2 1 3 3 4 6 5 7 6 10 7 12 8 13 9 15 10 18 11 21 12 22 13 25 14 27 15 28 16 31 17 33 18 36 19 40 20 42 21 43 22 45 23 46 24 48 25 55 26 57 27 60 28 61 29 66 30 67 31 70 32 73 33 75 34 78 35 81 36 82 37 87 38 88 39 90 40 91 41 97 42 103 43 105 44 106 45 108 46 111 47 112 48 117 49 120 50 123 51 126 52 127 53 130 54 132 55 133 56 138 57 145 58 147 59 148 60 150 61 157 62 160 63 165 64 166 65 168 66 171 67 175 68 178 69 181 70 183 71 186 72 190 73 192 74 196 75 201 76 202 77 207 78 208 79 211 80 213 81 216 82 220 83 222 84 223 85 225 86 231 87 235 88 237 89 241 90 243 91 246 92 252 93 253 94 262 95 265 96 270 97 273 98 276 99 277 100 280 101 285 102 288 103 291 104 292 105 295 106 298 107 300 108 301 109 307 110 312 111 313 112 315 113 318 114 321 115 322 116 328 117 330 118 333 119 337 120 342 121 346 122 351 123 355 124 358 125 361 126 363 127 367 128 370 129 372 130 376 131 378 132 385 133 390 134 396 135 397 136 402 137 403 138 405 139 406 140 411 141 418 142 420 143 421 144 423 145 430 146 432 147 433 148 435 149 445 150 447 151 451 152 456 153 460 154 462 155 465 156 468 157 475 158 477 159 480 160 483 161 487 162 490 163 496 164 498 165 501 166 502 167 507 168 508 169 511 170 516 171 517 172 522 173 523 174 526 175 535 176 537 177 538 178 540 179 543 180 546 181 550 182 553 183 556 184 567 185 568 186 573 187 577 188 582 189 585 190 588 191 592 192 598 193 600 194 603 195 606 196 607 197 610 198 616 199 621 200 630 201 631 202 633 203 636 204 637 205 640 206 642 207 643 208 645 209 651 210 652 211 655 212 672 213 675 214 678 215 682 216 691 217 696 218 703 219 705 220 706 221 708 222 711 223 715 224 717 225 718 226 721 227 727 228 732 229 733 230 735 231 736 232 738 233 741 234 747 235 753 236 757 237 763 238 766 239 768 240 771 241 775 242 777 243 781 244 783 245 790 246 792 247 795 248 796 249 798 250 801 251 802 252 805 253 810 254 820 255 823 256 825 257 826 258 838 259 840 260 841 261 846 262 852 263 853 264 858 265 862 266 865 267 868 268 871 269 880 270 883 271 885 272 886 273 892 274 897 275 903 276 907 277 915 278 922 279 925 280 927 281 928 282 930 283 931 284 936 285 942 286 945 287 948 288 957 289 958 290 966 291 967 292 978 293 981 294 985 295 988 296 990 297 991 298 993 299 997 300 1000 301 1005 302 1006 303 1011 304 1018 305 1023 306 1026 307 1032 308 1033 309 1035 310 1036 311 1041 312 1047 313 1048 314 1056 315 1057 316 1060 317 1062 318 1063 319 1068 320 1072 321 1081 322 1093 323 1095 324 1098 325 1102 326 1110 327 1111 328 1113 329 1117 330 1125 331 1126 332 1128 333 1132 334 1135 335 1138 336 1140 337 1146 338 1147 339 1158 340 1161 341 1162 342 1165 343 1167 344 1170 345 1177 346 1180 347 1182 348 1183 349 1186 350 1188 351 1191 352 1197 353 1200 354 1203 355 1210 356 1212 357 1215 358 1221 359 1225 360 1228 361 1230 362 1243 363 1252 364 1257 365 1261 366 1263 367 1266 368 1267 369 1270 370 1281 371 1287 372 1288 373 1296 374 1300 375 1302 376 1308 377 1315 378 1320 379 1321 380 1323 381 1327 382 1330 383 1333 384 1335 385 1336 386 1338 387 1341 388 1345 389 1347 390 1348 391 1351 392 1356 393 1357 394 1362 395 1366 396 1368 397 1375 398 1380 399 1386 400 1387 401 1390 402 1392 403 1393 404 1401 405 1408 406 1410 407 1413 408 1417 409 1420 410 1422 411 1431 412 1435 413 1440 414 1443 415 1446 416 1450 417 1455 418 1461 419 1468 420 1470 421 1473 422 1476 423 1477 424 1491 425 1492 426 1497 427 1501 428 1503 429 1510 430 1512 431 1516 432 1522 433 1525 434 1531 435 1533 436 1536 437 1546 438 1551 439 1552 440 1560 441 1573 442 1575 443 1576 444 1582 445 1585 446 1587 447 1593 448 1596 449 1600 450 1602 451 1606 452 1617 453 1618 454 1620 455 1621 456 1627 457 1641 458 1642 459 1645 460 1648 461 1651 462 1653 463 1656 464 1657 465 1663 466 1665 467 1671 468 1672 469 1677 470 1678 471 1686 472 1687 473 1695 474 1698 475 1708 476 1716 477 1720 478 1722 479 1723 480 1725 481 1726 482 1737 483 1741 484 1747 485 1750 486 1755 487 1756 488 1758 489 1761 490 1762 491 1765 492 1770 493 1771 494 1777 495 1782 496 1783 497 1788 498 1795 499 1798 500 1800 501 1803 502 1807 503 1810 504 1813 505 1821 506 1827 507 1828 508 1830 509 1837 510 1840 511 1842 512 1846 513 1851 514 1855 515 1858 516 1861 517 1872 518 1875 519 1876 520 1881 521 1888 522 1890 523 1893 524 1902 525 1903 526 1908 527 1915 528 1917 529 1918 530 1923 531 1930 532 1932 533 1936 534 1945 535 1947 536 1950 537 1951 538 1953 539 1956 540 1957 541 1963 542 1965 543 1975 544 1986 545 1992 546 1993 547 1995 548 1998 549 2001 550 2002 551 2005 552 2016 553 2017 554 2020 555 2028 556 2031 557 2037 558 2038 559 2041 560 2047 561 2055 562 2056 563 2058 564 2061 565 2068 566 2070 567 2071 568 2080 569 2092 570 2097 571 2100 572 2101 573 2106 574 2107 575 2112 576 2113 577 2118 578 2121 579 2122 580 2127 581 2128 582 2133 583 2136 584 2140 585 2155 586 2160 587 2161 588 2166 589 2170 590 2173 591 2178 592 2187 593 2190 594 2196 595 2202 596 2203 597 2212 598 2215 599 2217 600 2220 601 2223 602 2232 603 2233 604 2238 605 2245 606 2248 607 2250 608 2251 609 2253 610 2265 611 2266 612 2272 613 2275 614 2283 615 2287 616 2290 617 2293 618 2302 619 2310 620 2311 621 2313 622 2316 623 2317 624 2320 625 2323 626 2328 627 2331 628 2337 629 2343 630 2352 631 2353 632 2356 633 2358 634 2367 635 2371 636 2383 637 2385 638 2386 639 2388 640 2391 641 2392 642 2398 643 2400 644 2407 645 2422 646 2427 647 2430 648 2436 649 2443 650 2446 651 2451 652 2457 653 2458 654 2460 655 2463 656 2467 657 2470 658 2475 659 2476 660 2478 661 2485 662 2488 663 2491 664 2493 665 2496 666 2497 667 2502 668 2503 669 2511 670 2517 671 2521 672 2530 673 2532 674 2535 675 2541 676 2542 677 2545 678 2548 679 2551 680 2565 681 2568 682 2575 683 2577 684 2581 685 2586 686 2590 687 2596 688 2605 689 2607 690 2608 691 2610 692 2622 693 2628 694 2631 695 2632 696 2640 697 2643 698 2646 699 2653 700 2658 701 2665 702 2667 703 2682 704 2685 705 2688 706 2691 707 2695 708 2698 709 2700 710 2701 711 2707 712 2710 713 2712 714 2713 715 2716 716 2727 717 2730 718 2731 719 2733 720 2742 721 2743 722 2745 723 2751 724 2752 725 2755 726 2757 727 2770 728 2773 729 2776 730 2778 731 2782 732 2787 733 2803 734 2811 735 2812 736 2815 737 2817 738 2818 739 2820 740 2821 741 2826 742 2833 743 2836 744 2838 745 2842 746 2847 747 2850 748 2860 749 2862 750 2863 751 2866 752 2881 753 2883 754 2887 755 2892 756 2895 757 2898 758 2902 759 2905 760 2911 761 2913 762 2916 763 2917 764 2920 765 2922 766 2925 767 2926 768 2931 769 2932 770 2940 771 2943 772 2953 773 2955 774 2961 775 2968 776 2982 777 2985 778 2995 779 2997 780 3006 781 3010 782 3013 783 3015 784 3018 785 3025 786 3028 787 3031 788 3036 789 3037 790 3042 791 3048 792 3052 793 3057 794 3058 795 3063 796 3067 797 3073 798 3078 799 3090 800 3091 801 3093 802 3097 803 3100 804 3102 805 3106 806 3115 807 3120 808 3123 809 3126 810 3127 811 3130 812 3135 813 3141 814 3142 815 3147 816 3150 817 3153 818 3156 819 3160 820 3163 821 3168 822 3171 823 3172 824 3175 825 3178 826 3181 827 3186 828 3190 829 3202 830 3205 831 3216 832 3217 833 3226 834 3228 835 3232 836 3237 837 3252 838 3256 839 3265 840 3267 841 3268 842 3273 843 3276 844 3277 845 3280 846 3282 847 3291 848 3295 849 3301 850 3310 851 3318 852 3321 853 3322 854 3328 855 3331 856 3336 857 3337 858 3342 859 3343 860 3346 861 3351 862 3358 863 3360 864 3372 865 3373 866 3381 867 3382 868 3387 869 3388 870 3393 871 3403 872 3405 873 3406 874 3408 875 3412 876 3420 877 3423 878 3426 879 3427 880 3433 881 3441 882 3445 883 3447 884 3450 885 3465 886 3466 887 3471 888 3472 889 3475 890 3477 891 3480 892 3483 893 3487 894 3490 895 3492 896 3498 897 3501 898 3505 899 3511 900 3513 901 3520 902 3526 903 3531 904 3543 905 3546 906 3552 907 3555 908 3556 909 3567 910 3571 911 3580 912 3585 913 3588 914 3595 915 3597 916 3598 917 3601 918 3606 919 3610 920 3613 921 3615 922 3618 923 3633 924 3640 925 3645 926 3646 927 3652 928 3657 929 3658 930 3666 931 3667 932 3676 933 3688 934 3697 935 3700 936 3708 937 3717 938 3720 939 3721 940 3730 941 3732 942 3735 943 3736 944 3741 945 3745 946 3750 947 3753 948 3756 949 3760 950 3762 951 3765 952 3766 953 3771 954 3772 955 3778 956 3780 957 3783 958 3786 959 3787 960 3793 961 3795 962 3802 963 3811 964 3813 965 3816 966 3826 967 3828 968 3832 969 3835 970 3837 971 3841 972 3843 973 3850 974 3853 975 3855 976 3862 977 3868 978 3870 979 3871 980 3886 981 3888 982 3900 983 3903 984 3906 985 3912 986 3918 987 3925 988 3928 989 3930 990 3931 991 3933 992 3942 993 3945 994 3951 995 3955 996 3958 997 3960 998 3966 999 3967 1000 3973