1 0 2 1 3 3 4 5 5 8 6 9 7 11 8 13 9 16 10 17 11 19 12 21 13 24 14 25 15 27 16 29 17 32 18 33 19 35 20 37 21 40 22 41 23 43 24 45 25 48 26 49 27 51 28 53 29 56 30 57 31 59 32 61 33 64 34 65 35 67 36 69 37 72 38 73 39 75 40 77 41 80 42 81 43 83 44 85 45 88 46 89 47 91 48 93 49 96 50 97 51 99 52 101 53 104 54 105 55 107 56 109 57 112 58 113 59 115 60 117 61 120 62 121 63 123 64 125 65 128 66 129 67 131 68 133 69 136 70 137 71 139 72 141 73 144 74 145 75 147 76 149 77 152 78 153 79 155 80 157 81 160 82 161 83 163 84 165 85 168 86 169 87 171 88 173 89 176 90 177 91 179 92 181 93 184 94 185 95 187 96 189 97 192 98 193 99 195 100 197 101 200 102 201 103 203 104 205 105 208 106 209 107 211 108 213 109 216 110 217 111 219 112 221 113 224 114 225 115 227 116 229 117 232 118 233 119 235 120 237 121 240 122 241 123 243 124 245 125 248 126 249 127 251 128 253 129 256 130 257 131 259 132 261 133 264 134 265 135 267 136 269 137 272 138 273 139 275 140 277 141 280 142 281 143 283 144 285 145 288 146 289 147 291 148 293 149 296 150 297 151 299 152 301 153 304 154 305 155 307 156 309 157 312 158 313 159 315 160 317 161 320 162 321 163 323 164 325 165 328 166 329 167 331 168 333 169 336 170 337 171 339 172 341 173 344 174 345 175 347 176 349 177 352 178 353 179 355 180 357 181 360 182 361 183 363 184 365 185 368 186 369 187 371 188 373 189 376 190 377 191 379 192 381 193 384 194 385 195 387 196 389 197 392 198 393 199 395 200 397 201 400 202 401 203 403 204 405 205 408 206 409 207 411 208 413 209 416 210 417 211 419 212 421 213 424 214 425 215 427 216 429 217 432 218 433 219 435 220 437 221 440 222 441 223 443 224 445 225 448 226 449 227 451 228 453 229 456 230 457 231 459 232 461 233 464 234 465 235 467 236 469 237 472 238 473 239 475 240 477 241 480 242 481 243 483 244 485 245 488 246 489 247 491 248 493 249 496 250 497 251 499 252 501 253 504 254 505 255 507 256 509 257 512 258 513 259 515 260 517 261 520 262 521 263 523 264 525 265 528 266 529 267 531 268 533 269 536 270 537 271 539 272 541 273 544 274 545 275 547 276 549 277 552 278 553 279 555 280 557 281 560 282 561 283 563 284 565 285 568 286 569 287 571 288 573 289 576 290 577 291 579 292 581 293 584 294 585 295 587 296 589 297 592 298 593 299 595 300 597 301 600 302 601 303 603 304 605 305 608 306 609 307 611 308 613 309 616 310 617 311 619 312 621 313 624 314 625 315 627 316 629 317 632 318 633 319 635 320 637 321 640 322 641 323 643 324 645 325 648 326 649 327 651 328 653 329 656 330 657 331 659 332 661 333 664 334 665 335 667 336 669 337 672 338 673 339 675 340 677 341 680 342 681 343 683 344 685 345 688 346 689 347 691 348 693 349 696 350 697 351 699 352 701 353 704 354 705 355 707 356 709 357 712 358 713 359 715 360 717 361 720 362 721 363 723 364 725 365 728 366 729 367 731 368 733 369 736 370 737 371 739 372 741 373 744 374 745 375 747 376 749 377 752 378 753 379 755 380 757 381 760 382 761 383 763 384 765 385 768 386 769 387 771 388 773 389 776 390 777 391 779 392 781 393 784 394 785 395 787 396 789 397 792 398 793 399 795 400 797 401 800 402 801 403 803 404 805 405 808 406 809 407 811 408 813 409 816 410 817 411 819 412 821 413 824 414 825 415 827 416 829 417 832 418 833 419 835 420 837 421 840 422 841 423 843 424 845 425 848 426 849 427 851 428 853 429 856 430 857 431 859 432 861 433 864 434 865 435 867 436 869 437 872 438 873 439 875 440 877 441 880 442 881 443 883 444 885 445 888 446 889 447 891 448 893 449 896 450 897 451 899 452 901 453 904 454 905 455 907 456 909 457 912 458 913 459 915 460 917 461 920 462 921 463 923 464 925 465 928 466 929 467 931 468 933 469 936 470 937 471 939 472 941 473 944 474 945 475 947 476 949 477 952 478 953 479 955 480 957 481 960 482 961 483 963 484 965 485 968 486 969 487 971 488 973 489 976 490 977 491 979 492 981 493 984 494 985 495 987 496 989 497 992 498 993 499 995 500 997 501 1000 502 1001 503 1003 504 1005 505 1008 506 1009 507 1011 508 1013 509 1016 510 1017 511 1019 512 1021 513 1024 514 1025 515 1027 516 1029 517 1032 518 1033 519 1035 520 1037 521 1040 522 1041 523 1043 524 1045 525 1048 526 1049 527 1051 528 1053 529 1056 530 1057 531 1059 532 1061 533 1064 534 1065 535 1067 536 1069 537 1072 538 1073 539 1075 540 1077 541 1080 542 1081 543 1083 544 1085 545 1088 546 1089 547 1091 548 1093 549 1096 550 1097 551 1099 552 1101 553 1104 554 1105 555 1107 556 1109 557 1112 558 1113 559 1115 560 1117 561 1120 562 1121 563 1123 564 1125 565 1128 566 1129 567 1131 568 1133 569 1136 570 1137 571 1139 572 1141 573 1144 574 1145 575 1147 576 1149 577 1152 578 1153 579 1155 580 1157 581 1160 582 1161 583 1163 584 1165 585 1168 586 1169 587 1171 588 1173 589 1176 590 1177 591 1179 592 1181 593 1184 594 1185 595 1187 596 1189 597 1192 598 1193 599 1195 600 1197 601 1200 602 1201 603 1203 604 1205 605 1208 606 1209 607 1211 608 1213 609 1216 610 1217 611 1219 612 1221 613 1224 614 1225 615 1227 616 1229 617 1232 618 1233 619 1235 620 1237 621 1240 622 1241 623 1243 624 1245 625 1248 626 1249 627 1251 628 1253 629 1256 630 1257 631 1259 632 1261 633 1264 634 1265 635 1267 636 1269 637 1272 638 1273 639 1275 640 1277 641 1280 642 1281 643 1283 644 1285 645 1288 646 1289 647 1291 648 1293 649 1296 650 1297 651 1299 652 1301 653 1304 654 1305 655 1307 656 1309 657 1312 658 1313 659 1315 660 1317 661 1320 662 1321 663 1323 664 1325 665 1328 666 1329 667 1331 668 1333 669 1336 670 1337 671 1339 672 1341 673 1344 674 1345 675 1347 676 1349 677 1352 678 1353 679 1355 680 1357 681 1360 682 1361 683 1363 684 1365 685 1368 686 1369 687 1371 688 1373 689 1376 690 1377 691 1379 692 1381 693 1384 694 1385 695 1387 696 1389 697 1392 698 1393 699 1395 700 1397 701 1400 702 1401 703 1403 704 1405 705 1408 706 1409 707 1411 708 1413 709 1416 710 1417 711 1419 712 1421 713 1424 714 1425 715 1427 716 1429 717 1432 718 1433 719 1435 720 1437 721 1440 722 1441 723 1443 724 1445 725 1448 726 1449 727 1451 728 1453 729 1456 730 1457 731 1459 732 1461 733 1464 734 1465 735 1467 736 1469 737 1472 738 1473 739 1475 740 1477 741 1480 742 1481 743 1483 744 1485 745 1488 746 1489 747 1491 748 1493 749 1496 750 1497 751 1499 752 1501 753 1504 754 1505 755 1507 756 1509 757 1512 758 1513 759 1515 760 1517 761 1520 762 1521 763 1523 764 1525 765 1528 766 1529 767 1531 768 1533 769 1536 770 1537 771 1539 772 1541 773 1544 774 1545 775 1547 776 1549 777 1552 778 1553 779 1555 780 1557 781 1560 782 1561 783 1563 784 1565 785 1568 786 1569 787 1571 788 1573 789 1576 790 1577 791 1579 792 1581 793 1584 794 1585 795 1587 796 1589 797 1592 798 1593 799 1595 800 1597 801 1600 802 1601 803 1603 804 1605 805 1608 806 1609 807 1611 808 1613 809 1616 810 1617 811 1619 812 1621 813 1624 814 1625 815 1627 816 1629 817 1632 818 1633 819 1635 820 1637 821 1640 822 1641 823 1643 824 1645 825 1648 826 1649 827 1651 828 1653 829 1656 830 1657 831 1659 832 1661 833 1664 834 1665 835 1667 836 1669 837 1672 838 1673 839 1675 840 1677 841 1680 842 1681 843 1683 844 1685 845 1688 846 1689 847 1691 848 1693 849 1696 850 1697 851 1699 852 1701 853 1704 854 1705 855 1707 856 1709 857 1712 858 1713 859 1715 860 1717 861 1720 862 1721 863 1723 864 1725 865 1728 866 1729 867 1731 868 1733 869 1736 870 1737 871 1739 872 1741 873 1744 874 1745 875 1747 876 1749 877 1752 878 1753 879 1755 880 1757 881 1760 882 1761 883 1763 884 1765 885 1768 886 1769 887 1771 888 1773 889 1776 890 1777 891 1779 892 1781 893 1784 894 1785 895 1787 896 1789 897 1792 898 1793 899 1795 900 1797 901 1800 902 1801 903 1803 904 1805 905 1808 906 1809 907 1811 908 1813 909 1816 910 1817 911 1819 912 1821 913 1824 914 1825 915 1827 916 1829 917 1832 918 1833 919 1835 920 1837 921 1840 922 1841 923 1843 924 1845 925 1848 926 1849 927 1851 928 1853 929 1856 930 1857 931 1859 932 1861 933 1864 934 1865 935 1867 936 1869 937 1872 938 1873 939 1875 940 1877 941 1880 942 1881 943 1883 944 1885 945 1888 946 1889 947 1891 948 1893 949 1896 950 1897 951 1899 952 1901 953 1904 954 1905 955 1907 956 1909 957 1912 958 1913 959 1915 960 1917 961 1920 962 1921 963 1923 964 1925 965 1928 966 1929 967 1931 968 1933 969 1936 970 1937 971 1939 972 1941 973 1944 974 1945 975 1947 976 1949 977 1952 978 1953 979 1955 980 1957 981 1960 982 1961 983 1963 984 1965 985 1968 986 1969 987 1971 988 1973 989 1976 990 1977 991 1979 992 1981 993 1984 994 1985 995 1987 996 1989 997 1992 998 1993 999 1995 1000 1997