1 1 2 2 3 4 4 5 5 8 6 10 7 11 8 16 9 17 10 20 11 22 12 23 13 25 14 31 15 32 16 34 17 40 18 41 19 44 20 46 21 47 22 50 23 55 24 59 25 62 26 64 27 67 28 68 29 73 30 80 31 82 32 83 33 85 34 88 35 92 36 94 37 97 38 100 39 103 40 109 41 110 42 115 43 118 44 121 45 124 46 125 47 127 48 128 49 134 50 136 51 137 52 146 53 149 54 155 55 157 56 160 57 164 58 166 59 167 60 170 61 176 62 179 63 184 64 187 65 188 66 191 67 194 68 197 69 200 70 205 71 206 72 211 73 218 74 220 75 227 76 230 77 233 78 235 79 236 80 241 81 242 82 248 83 250 84 253 85 254 86 256 87 257 88 268 89 269 90 272 91 274 92 275 93 277 94 283 95 289 96 292 97 295 98 298 99 307 100 310 101 313 102 314 103 320 104 328 105 331 106 332 107 334 108 335 109 340 110 341 111 347 112 352 113 353 114 358 115 365 116 367 117 368 118 374 119 376 120 379 121 382 122 388 123 389 124 391 125 394 126 400 127 401 128 410 129 412 130 415 131 419 132 422 133 425 134 431 135 436 136 439 137 440 138 449 139 451 140 454 141 460 142 461 143 466 144 467 145 470 146 472 147 482 148 484 149 485 150 487 151 496 152 499 153 500 154 506 155 508 156 509 157 512 158 514 159 515 160 517 161 523 162 527 163 529 164 536 165 538 166 544 167 545 168 547 169 548 170 550 171 554 172 563 173 566 174 571 175 575 176 578 177 584 178 587 179 590 180 596 181 599 182 605 183 607 184 614 185 617 186 620 187 625 188 626 189 628 190 631 191 635 192 640 193 643 194 649 195 653 196 656 197 661 198 662 199 664 200 668 201 670 202 677 203 680 204 682 205 685 206 691 207 694 208 697 209 704 210 706 211 709 212 713 213 716 214 727 215 730 216 734 217 736 218 737 219 739 220 745 221 748 222 751 223 752 224 758 225 761 226 764 227 773 228 775 229 776 230 778 231 782 232 785 233 788 234 797 235 799 236 800 237 802 238 803 239 811 240 820 241 823 242 824 243 829 244 830 245 835 246 838 247 844 248 850 249 853 250 859 251 862 252 872 253 877 254 878 255 880 256 883 257 895 258 898 259 902 260 907 261 908 262 913 263 919 264 920 265 922 266 932 267 934 268 935 269 937 270 940 271 943 272 944 273 947 274 955 275 961 276 964 277 967 278 968 279 970 280 974 281 977 282 985 283 991 284 992 285 998 286 1000 287 1003 288 1009 289 1012 290 1016 291 1018 292 1019 293 1024 294 1025 295 1028 296 1030 297 1031 298 1034 299 1039 300 1046 301 1051 302 1054 303 1055 304 1058 305 1063 306 1067 307 1072 308 1076 309 1081 310 1087 311 1088 312 1090 313 1093 314 1094 315 1096 316 1100 317 1103 318 1108 319 1117 320 1126 321 1129 322 1132 323 1133 324 1135 325 1139 326 1142 327 1150 328 1153 329 1156 330 1165 331 1168 332 1171 333 1174 334 1175 335 1180 336 1187 337 1192 338 1198 339 1199 340 1201 341 1205 342 1210 343 1214 344 1217 345 1228 346 1229 347 1234 348 1237 349 1240 350 1241 351 1250 352 1252 353 1256 354 1259 355 1262 356 1265 357 1270 358 1271 359 1279 360 1280 361 1285 362 1286 363 1289 364 1297 365 1298 366 1303 367 1306 368 1312 369 1319 370 1322 371 1324 372 1327 373 1328 374 1331 375 1336 376 1340 377 1345 378 1354 379 1357 380 1360 381 1364 382 1367 383 1370 384 1375 385 1381 386 1382 387 1385 388 1388 389 1394 390 1397 391 1408 392 1409 393 1411 394 1412 395 1415 396 1418 397 1426 398 1427 399 1432 400 1433 401 1445 402 1447 403 1453 404 1454 405 1457 406 1460 407 1468 408 1471 409 1472 410 1474 411 1475 412 1478 413 1483 414 1489 415 1490 416 1496 417 1499 418 1502 419 1504 420 1507 421 1516 422 1522 423 1523 424 1528 425 1535 426 1541 427 1543 428 1546 429 1550 430 1552 431 1553 432 1556 433 1564 434 1565 435 1567 436 1570 437 1576 438 1579 439 1594 440 1597 441 1598 442 1600 443 1604 444 1606 445 1607 446 1613 447 1621 448 1622 449 1637 450 1639 451 1640 452 1646 453 1648 454 1649 455 1655 456 1658 457 1660 458 1663 459 1669 460 1670 461 1675 462 1676 463 1679 464 1681 465 1688 466 1697 467 1700 468 1705 469 1706 470 1709 471 1718 472 1723 473 1724 474 1727 475 1735 476 1741 477 1744 478 1751 479 1753 480 1754 481 1756 482 1760 483 1765 484 1766 485 1777 486 1787 487 1790 488 1796 489 1801 490 1804 491 1814 492 1816 493 1823 494 1825 495 1826 496 1829 497 1835 498 1837 499 1838 500 1840 501 1844 502 1847 503 1853 504 1864 505 1867 506 1868 507 1870 508 1873 509 1874 510 1879 511 1880 512 1886 513 1888 514 1894 515 1895 516 1901 517 1909 518 1910 519 1913 520 1922 521 1927 522 1928 523 1933 524 1934 525 1936 526 1940 527 1945 528 1948 529 1951 530 1954 531 1955 532 1969 533 1970 534 1979 535 1982 536 1984 537 1993 538 1996 539 1999 540 2000 541 2005 542 2006 543 2011 544 2018 545 2024 546 2027 547 2032 548 2036 549 2038 550 2039 551 2048 552 2050 553 2056 554 2057 555 2060 556 2062 557 2063 558 2068 559 2075 560 2077 561 2078 562 2081 563 2087 564 2092 565 2095 566 2099 567 2101 568 2102 569 2108 570 2110 571 2113 572 2116 573 2125 574 2126 575 2131 576 2134 577 2141 578 2144 579 2152 580 2153 581 2155 582 2159 583 2162 584 2167 585 2174 586 2176 587 2179 588 2180 589 2186 590 2188 591 2192 592 2195 593 2200 594 2206 595 2207 596 2209 597 2216 598 2221 599 2231 600 2234 601 2239 602 2245 603 2251 604 2252 605 2255 606 2258 607 2263 608 2264 609 2266 610 2269 611 2270 612 2278 613 2281 614 2284 615 2293 616 2300 617 2305 618 2306 619 2309 620 2312 621 2321 622 2329 623 2330 624 2333 625 2335 626 2336 627 2341 628 2342 629 2348 630 2350 631 2351 632 2360 633 2369 634 2371 635 2374 636 2381 637 2384 638 2389 639 2396 640 2398 641 2399 642 2402 643 2410 644 2417 645 2419 646 2420 647 2425 648 2428 649 2434 650 2435 651 2437 652 2447 653 2456 654 2458 655 2467 656 2468 657 2474 658 2477 659 2480 660 2482 661 2495 662 2497 663 2500 664 2504 665 2507 666 2512 667 2518 668 2521 669 2524 670 2530 671 2533 672 2539 673 2540 674 2542 675 2545 676 2549 677 2557 678 2558 679 2560 680 2563 681 2570 682 2572 683 2573 684 2575 685 2578 686 2585 687 2591 688 2594 689 2596 690 2606 691 2609 692 2612 693 2615 694 2621 695 2624 696 2635 697 2638 698 2644 699 2645 700 2647 701 2648 702 2651 703 2654 704 2656 705 2659 706 2662 707 2669 708 2671 709 2672 710 2680 711 2683 712 2689 713 2690 714 2699 715 2708 716 2711 717 2714 718 2719 719 2720 720 2725 721 2728 722 2731 723 2734 724 2735 725 2740 726 2747 727 2749 728 2750 729 2762 730 2764 731 2767 732 2770 733 2773 734 2776 735 2783 736 2788 737 2789 738 2794 739 2797 740 2803 741 2815 742 2816 743 2818 744 2822 745 2824 746 2827 747 2830 748 2833 749 2836 750 2839 751 2843 752 2852 753 2854 754 2855 755 2857 756 2864 757 2866 758 2875 759 2879 760 2890 761 2894 762 2897 763 2906 764 2908 765 2909 766 2914 767 2920 768 2921 769 2927 770 2935 771 2936 772 2942 773 2944 774 2948 775 2950 776 2953 777 2956 778 2959 779 2963 780 2966 781 2971 782 2978 783 2980 784 2992 785 2993 786 2995 787 2998 788 3001 789 3004 790 3007 791 3008 792 3014 793 3019 794 3025 795 3032 796 3035 797 3037 798 3043 799 3044 800 3046 801 3047 802 3049 803 3056 804 3067 805 3070 806 3082 807 3083 808 3085 809 3086 810 3092 811 3100 812 3104 813 3106 814 3109 815 3112 816 3113 817 3121 818 3125 819 3128 820 3130 821 3134 822 3140 823 3149 824 3151 825 3152 826 3155 827 3158 828 3163 829 3169 830 3175 831 3179 832 3187 833 3188 834 3193 835 3194 836 3196 837 3200 838 3203 839 3208 840 3212 841 3214 842 3215 843 3217 844 3226 845 3229 846 3242 847 3244 848 3245 849 3247 850 3253 851 3259 852 3265 853 3274 854 3278 855 3280 856 3292 857 3296 858 3298 859 3299 860 3305 861 3307 862 3310 863 3316 864 3319 865 3320 866 3326 867 3329 868 3338 869 3340 870 3343 871 3349 872 3350 873 3352 874 3358 875 3359 876 3362 877 3371 878 3376 879 3377 880 3379 881 3385 882 3389 883 3394 884 3400 885 3403 886 3407 887 3410 888 3412 889 3418 890 3425 891 3427 892 3431 893 3433 894 3436 895 3443 896 3446 897 3448 898 3454 899 3455 900 3457 901 3463 902 3469 903 3470 904 3481 905 3482 906 3485 907 3488 908 3499 909 3502 910 3506 911 3508 912 3512 913 3517 914 3520 915 3529 916 3530 917 3532 918 3539 919 3545 920 3547 921 3554 922 3559 923 3565 924 3574 925 3580 926 3581 927 3587 928 3592 929 3593 930 3602 931 3608 932 3611 933 3613 934 3623 935 3628 936 3632 937 3635 938 3637 939 3641 940 3646 941 3650 942 3652 943 3658 944 3659 945 3670 946 3673 947 3674 948 3676 949 3680 950 3685 951 3688 952 3691 953 3694 954 3695 955 3701 956 3706 957 3719 958 3725 959 3728 960 3733 961 3734 962 3736 963 3740 964 3746 965 3748 966 3751 967 3755 968 3758 969 3760 970 3761 971 3769 972 3772 973 3776 974 3788 975 3790 976 3793 977 3802 978 3803 979 3805 980 3817 981 3818 982 3820 983 3823 984 3826 985 3841 986 3844 987 3847 988 3853 989 3854 990 3856 991 3859 992 3865 993 3866 994 3868 995 3872 996 3875 997 3877 998 3880 999 3883 1000 3889 1001 3890