1 1 2 3 3 5 4 8 5 10 6 12 7 15 8 17 9 19 10 22 11 24 12 26 13 29 14 31 15 33 16 36 17 38 18 40 19 43 20 45 21 47 22 50 23 52 24 54 25 57 26 59 27 61 28 64 29 66 30 68 31 71 32 73 33 75 34 78 35 80 36 82 37 85 38 87 39 89 40 92 41 94 42 96 43 99 44 101 45 103 46 106 47 108 48 110 49 113 50 115 51 117 52 120 53 122 54 124 55 127 56 129 57 131 58 134 59 136 60 138 61 141 62 143 63 145 64 148 65 150 66 152 67 155 68 157 69 159 70 162 71 164 72 166 73 169 74 171 75 173 76 176 77 178 78 180 79 183 80 185 81 187 82 190 83 192 84 194 85 197 86 199 87 201 88 204 89 206 90 208 91 211 92 213 93 215 94 218 95 220 96 222 97 225 98 227 99 229 100 232 101 234 102 236 103 239 104 241 105 243 106 246 107 248 108 250 109 253 110 255 111 257 112 260 113 262 114 264 115 267 116 269 117 271 118 274 119 276 120 278 121 281 122 283 123 285 124 288 125 290 126 292 127 295 128 297 129 299 130 302 131 304 132 306 133 309 134 311 135 313 136 316 137 318 138 320 139 323 140 325 141 327 142 330 143 332 144 334 145 337 146 339 147 341 148 344 149 346 150 348 151 351 152 353 153 355 154 358 155 360 156 362 157 365 158 367 159 369 160 372 161 374 162 376 163 379 164 381 165 383 166 386 167 388 168 390 169 393 170 395 171 397 172 400 173 402 174 404 175 407 176 409 177 411 178 414 179 416 180 418 181 421 182 423 183 425 184 428 185 430 186 432 187 435 188 437 189 439 190 442 191 444 192 446 193 449 194 451 195 453 196 456 197 458 198 460 199 463 200 465 201 467 202 470 203 472 204 474 205 477 206 479 207 481 208 484 209 486 210 488 211 491 212 493 213 495 214 498 215 500 216 502 217 505 218 507 219 509 220 512 221 514 222 516 223 519 224 521 225 523 226 526 227 528 228 530 229 533 230 535 231 537 232 540 233 542 234 544 235 547 236 549 237 551 238 554 239 556 240 558 241 561 242 563 243 565 244 568 245 570 246 572 247 575 248 577 249 579 250 582 251 584 252 586 253 589 254 591 255 593 256 596 257 598 258 600 259 603 260 605 261 607 262 610 263 612 264 614 265 617 266 619 267 621 268 624 269 626 270 628 271 631 272 633 273 635 274 638 275 640 276 642 277 645 278 647 279 649 280 652 281 654 282 656 283 659 284 661 285 663 286 666 287 668 288 670 289 673 290 675 291 677 292 680 293 682 294 684 295 687 296 689 297 691 298 694 299 696 300 698 301 701 302 703 303 705 304 708 305 710 306 712 307 715 308 717 309 719 310 722 311 724 312 726 313 729 314 731 315 733 316 736 317 738 318 740 319 743 320 745 321 747 322 750 323 752 324 754 325 757 326 759 327 761 328 764 329 766 330 768 331 771 332 773 333 775 334 778 335 780 336 782 337 785 338 787 339 789 340 792 341 794 342 796 343 799 344 801 345 803 346 806 347 808 348 810 349 813 350 815 351 817 352 820 353 822 354 824 355 827 356 829 357 831 358 834 359 836 360 838 361 841 362 843 363 845 364 848 365 850 366 852 367 855 368 857 369 859 370 862 371 864 372 866 373 869 374 871 375 873 376 876 377 878 378 880 379 883 380 885 381 887 382 890 383 892 384 894 385 897 386 899 387 901 388 904 389 906 390 908 391 911 392 913 393 915 394 918 395 920 396 922 397 925 398 927 399 929 400 932 401 934 402 936 403 939 404 941 405 943 406 946 407 948 408 950 409 953 410 955 411 957 412 960 413 962 414 964 415 967 416 969 417 971 418 974 419 976 420 978 421 981 422 983 423 985 424 988 425 990 426 992 427 995 428 997 429 999 430 1002 431 1004 432 1006 433 1009 434 1011 435 1013 436 1016 437 1018 438 1020 439 1023 440 1025 441 1027 442 1030 443 1032 444 1034 445 1037 446 1039 447 1041 448 1044 449 1046 450 1048 451 1051 452 1053 453 1055 454 1058 455 1060 456 1062 457 1065 458 1067 459 1069 460 1072 461 1074 462 1076 463 1079 464 1081 465 1083 466 1086 467 1088 468 1090 469 1093 470 1095 471 1097 472 1100 473 1102 474 1104 475 1107 476 1109 477 1111 478 1114 479 1116 480 1118 481 1121 482 1123 483 1125 484 1128 485 1130 486 1132 487 1135 488 1137 489 1139 490 1142 491 1144 492 1146 493 1149 494 1151 495 1153 496 1156 497 1158 498 1160 499 1163 500 1165 501 1167 502 1170 503 1172 504 1174 505 1177 506 1179 507 1181 508 1184 509 1186 510 1188 511 1191 512 1193 513 1195 514 1198 515 1200 516 1202 517 1205 518 1207 519 1209 520 1212 521 1214 522 1216 523 1219 524 1221 525 1223 526 1226 527 1228 528 1230 529 1233 530 1235 531 1237 532 1240 533 1242 534 1244 535 1247 536 1249 537 1251 538 1254 539 1256 540 1258 541 1261 542 1263 543 1265 544 1268 545 1270 546 1272 547 1275 548 1277 549 1279 550 1282 551 1284 552 1286 553 1289 554 1291 555 1293 556 1296 557 1298 558 1300 559 1303 560 1305 561 1307 562 1310 563 1312 564 1314 565 1317 566 1319 567 1321 568 1324 569 1326 570 1328 571 1331 572 1333 573 1335 574 1338 575 1340 576 1342 577 1345 578 1347 579 1349 580 1352 581 1354 582 1356 583 1359 584 1361 585 1363 586 1366 587 1368 588 1370 589 1373 590 1375 591 1377 592 1380 593 1382 594 1384 595 1387 596 1389 597 1391 598 1394 599 1396 600 1398 601 1401 602 1403 603 1405 604 1408 605 1410 606 1412 607 1415 608 1417 609 1419 610 1422 611 1424 612 1426 613 1429 614 1431 615 1433 616 1436 617 1438 618 1440 619 1443 620 1445 621 1447 622 1450 623 1452 624 1454 625 1457 626 1459 627 1461 628 1464 629 1466 630 1468 631 1471 632 1473 633 1475 634 1478 635 1480 636 1482 637 1485 638 1487 639 1489 640 1492 641 1494 642 1496 643 1499 644 1501 645 1503 646 1506 647 1508 648 1510 649 1513 650 1515 651 1517 652 1520 653 1522 654 1524 655 1527 656 1529 657 1531 658 1534 659 1536 660 1538 661 1541 662 1543 663 1545 664 1548 665 1550 666 1552 667 1555 668 1557 669 1559 670 1562 671 1564 672 1566 673 1569 674 1571 675 1573 676 1576 677 1578 678 1580 679 1583 680 1585 681 1587 682 1590 683 1592 684 1594 685 1597 686 1599 687 1601 688 1604 689 1606 690 1608 691 1611 692 1613 693 1615 694 1618 695 1620 696 1622 697 1625 698 1627 699 1629 700 1632 701 1634 702 1636 703 1639 704 1641 705 1643 706 1646 707 1648 708 1650 709 1653 710 1655 711 1657 712 1660 713 1662 714 1664 715 1667 716 1669 717 1671 718 1674 719 1676 720 1678 721 1681 722 1683 723 1685 724 1688 725 1690 726 1692 727 1695 728 1697 729 1699 730 1702 731 1704 732 1706 733 1709 734 1711 735 1713 736 1716 737 1718 738 1720 739 1723 740 1725 741 1727 742 1730 743 1732 744 1734 745 1737 746 1739 747 1741 748 1744 749 1746 750 1748 751 1751 752 1753 753 1755 754 1758 755 1760 756 1762 757 1765 758 1767 759 1769 760 1772 761 1774 762 1776 763 1779 764 1781 765 1783 766 1786 767 1788 768 1790 769 1793 770 1795 771 1797 772 1800 773 1802 774 1804 775 1807 776 1809 777 1811 778 1814 779 1816 780 1818 781 1821 782 1823 783 1825 784 1828 785 1830 786 1832 787 1835 788 1837 789 1839 790 1842 791 1844 792 1846 793 1849 794 1851 795 1853 796 1856 797 1858 798 1860 799 1863 800 1865 801 1867 802 1870 803 1872 804 1874 805 1877 806 1879 807 1881 808 1884 809 1886 810 1888 811 1891 812 1893 813 1895 814 1898 815 1900 816 1902 817 1905 818 1907 819 1909 820 1912 821 1914 822 1916 823 1919 824 1921 825 1923 826 1926 827 1928 828 1930 829 1933 830 1935 831 1937 832 1940 833 1942 834 1944 835 1947 836 1949 837 1951 838 1954 839 1956 840 1958 841 1961 842 1963 843 1965 844 1968 845 1970 846 1972 847 1975 848 1977 849 1979 850 1982 851 1984 852 1986 853 1989 854 1991 855 1993 856 1996 857 1998 858 2000 859 2003 860 2005 861 2007 862 2010 863 2012 864 2014 865 2017 866 2019 867 2021 868 2024 869 2026 870 2028 871 2031 872 2033 873 2035 874 2038 875 2040 876 2042 877 2045 878 2047 879 2049 880 2052 881 2054 882 2056 883 2059 884 2061 885 2063 886 2066 887 2068 888 2070 889 2073 890 2075 891 2077 892 2080 893 2082 894 2084 895 2087 896 2089 897 2091 898 2094 899 2096 900 2098 901 2101 902 2103 903 2105 904 2108 905 2110 906 2112 907 2115 908 2117 909 2119 910 2122 911 2124 912 2126 913 2129 914 2131 915 2133 916 2136 917 2138 918 2140 919 2143 920 2145 921 2147 922 2150 923 2152 924 2154 925 2157 926 2159 927 2161 928 2164 929 2166 930 2168 931 2171 932 2173 933 2175 934 2178 935 2180 936 2182 937 2185 938 2187 939 2189 940 2192 941 2194 942 2196 943 2199 944 2201 945 2203 946 2206 947 2208 948 2210 949 2213 950 2215 951 2217 952 2220 953 2222 954 2224 955 2227 956 2229 957 2231 958 2234 959 2236 960 2238 961 2241 962 2243 963 2245 964 2248 965 2250 966 2252 967 2255 968 2257 969 2259 970 2262 971 2264 972 2266 973 2269 974 2271 975 2273 976 2276 977 2278 978 2280 979 2283 980 2285 981 2287 982 2290 983 2292 984 2294 985 2297 986 2299 987 2301 988 2304 989 2306 990 2308 991 2311 992 2313 993 2315 994 2318 995 2320 996 2322 997 2325 998 2327 999 2329 1000 2332