0 1 1 2 2 4 3 7 4 5 5 8 6 10 7 14 8 15 9 19 10 16 11 20 12 21 13 22 14 27 15 30 16 28 17 33 18 32 19 38 20 37 21 39 22 44 23 45 24 51 25 46 26 47 27 54 28 55 29 52 30 59 31 62 32 60 33 64 34 50 35 67 36 72 37 78 38 74 39 68 40 81 41 82 42 80 43 85 44 79 45 87 46 86 47 91 48 90 49 94 50 102 51 98 52 103 53 99 54 105 55 100 56 108 57 112 58 110 59 113 60 127 61 128 62 125 63 133 64 118 65 123 66 134 67 136 68 130 69 120 70 144 71 131 72 137 73 141 74 138 75 146 76 147 77 143 78 156 79 155 80 158 81 157 82 160 83 174 84 167 85 153 86 169 87 171 88 180 89 179 90 182 91 170 92 175 93 178 94 186 95 183 96 187 97 189 98 188 99 197 100 191 101 195 102 199 103 203 104 207 105 209 106 206 107 212 108 215 109 214 110 219 111 213 112 224 113 225 114 226 115 217 116 229 117 227 118 230 119 228 120 236 121 235 122 237 123 239 124 242 125 244 126 247 127 249 128 252 129 260 130 259 131 262 132 263 133 269 134 254 135 277 136 265 137 283 138 267 139 271 140 276 141 273 142 282 143 285 144 274 145 292 146 281 147 287 148 295 149 286 150 298 151 301 152 300 153 304 154 303 155 305 156 306 157 307 158 308 159 314 160 321 161 318 162 316 163 328 164 319 165 324 166 326 167 323 168 335 169 332 170 336 171 338 172 333 173 344 174 342 175 343 176 347 177 348 178 356 179 349 180 354 181 355 182 360 183 367 184 362 185 363 186 371 187 372 188 366 189 375 190 373 191 381 192 368 193 389 194 392 195 387 196 382 197 390 198 397 199 393 200 391 201 395 202 399 203 407 204 398 205 412 206 405 207 408 208 400 209 411 210 414 211 421 212 423 213 417 214 420 215 430 216 422 217 424 218 435 219 431 220 436 221 440 222 438 223 444 224 439 225 441 226 447 227 452 228 453 229 448 230 461 231 460 232 466 233 454 234 462 235 465 236 467 237 470 238 468 239 473 240 474 241 477 242 482 243 480 244 483 245 488 246 490 247 478 248 494 249 497 250 485 251 499 252 493 253 500 254 502 255 503 256 504 257 505 258 510 259 513 260 515 261 507 262 517 263 522 264 526 265 518 266 533 267 529 268 535 269 524 270 534 271 537 272 528 273 540 274 544 275 551 276 558 277 552 278 553 279 554 280 564 281 565 282 556 283 575 284 562 285 570 286 572 287 561 288 569 289 574 290 571 291 578 292 580 293 579 294 587 295 586 296 588 297 590 298 594 299 592 300 602 301 595 302 598 303 593 304 605 305 609 306 600 307 612 308 614 309 616 310 620 311 618 312 617 313 625 314 621 315 623 316 626 317 627 318 629 319 619 320 631 321 630 322 633 323 636 324 640 325 645 326 655 327 657 328 648 329 638 330 654 331 664 332 653 333 663 334 670 335 660 336 678 337 665 338 666 339 673 340 679 341 672 342 682 343 680 344 681 345 683 346 684 347 692 348 694 349 687 350 693 351 696 352 700 353 706 354 699 355 712 356 701 357 716 358 718 359 702 360 724 361 714 362 707 363 721 364 719 365 726 366 722 367 730 368 732 369 731 370 736 371 728 372 737 373 747 374 740 375 750 376 755 377 742 378 744 379 751 380 760 381 752 382 756 383 763 384 759 385 758 386 765 387 764 388 766 389 768 390 775 391 770 392 782 393 783 394 778 395 785 396 777 397 789 398 792 399 791 400 795 401 798 402 799 403 800 404 802 405 801 406 803 407 814 408 818 409 816 410 819 411 821 412 807 413 824 414 823 415 820 416 828 417 827 418 829 419 832 420 834 421 848 422 851 423 842 424 843 425 849 426 839 427 857 428 853 429 836 430 847 431 861 432 854 433 855 434 858 435 864 436 868 437 863 438 872 439 873 440 877 441 871 442 875 443 881 444 885 445 879 446 890 447 891 448 893 449 892 450 896 451 897 452 895 453 903 454 898 455 914 456 904 457 907 458 906 459 917 460 910 461 911 462 924 463 928 464 912 465 929 466 931 467 918 468 930 469 933 470 940 471 936 472 919 473 939 474 923 475 944 476 942 477 945 478 949 479 946 480 950 481 952 482 960 483 969 484 954 485 961 486 966 487 965 488 970 489 975 490 980 491 974 492 976 493 981 494 986 495 988 496 983 497 989 498 994 499 996 500 998 501 995 502 1004 503 1000 504 1006 505 1008 506 1010 507 999 508 1014 509 1012 510 1011 511 1016 512 1021 513 1026 514 1017 515 1018 516 1027 517 1033 518 1029 519 1035 520 1037 521 1036 522 1034 523 1042 524 1043 525 1038 526 1041 527 1050 528 1049 529 1056 530 1045 531 1061 532 1060 533 1070 534 1067 535 1072 536 1066 537 1074 538 1069 539 1075 540 1076 541 1077 542 1078 543 1079 544 1081 545 1086 546 1083 547 1087 548 1091 549 1092 550 1093 551 1094 552 1097 553 1099 554 1100 555 1101 556 1102 557 1106 558 1108 559 1114 560 1113 561 1115 562 1116 563 1119 564 1111 565 1123 566 1135 567 1124 568 1138 569 1127 570 1134 571 1144 572 1112 573 1128 574 1148 575 1153 576 1155 577 1147 578 1146 579 1151 580 1152 581 1162 582 1154 583 1156 584 1168 585 1167 586 1164 587 1176 588 1161 589 1169 590 1180 591 1171 592 1170 593 1185 594 1175 595 1189 596 1177 597 1179 598 1203 599 1190 600 1195 601 1192 602 1207 603 1196 604 1201 605 1208 606 1202 607 1204 608 1213 609 1217 610 1210 611 1221 612 1216 613 1220 614 1222 615 1218 616 1229 617 1225 618 1223 619 1227 620 1231 621 1232 622 1239 623 1233 624 1251 625 1241 626 1254 627 1245 628 1255 629 1259 630 1258 631 1262 632 1265 633 1268 634 1266 635 1264 636 1272 637 1267 638 1270 639 1279 640 1271 641 1275 642 1280 643 1277 644 1281 645 1282 646 1284 647 1287 648 1297 649 1296 650 1294 651 1288 652 1298 653 1301 654 1295 655 1309 656 1302 657 1306 658 1310 659 1314 660 1311 661 1319 662 1321 663 1313 664 1332 665 1320 666 1322 667 1324 668 1323 669 1344 670 1327 671 1334 672 1341 673 1337 674 1355 675 1340 676 1350 677 1346 678 1360 679 1347 680 1365 681 1356 682 1359 683 1349 684 1368 685 1369 686 1366 687 1370 688 1372 689 1373 690 1377 691 1382 692 1383 693 1374 694 1379 695 1384 696 1388 697 1378 698 1390 699 1387 700 1391 701 1392 702 1394 703 1393 704 1398 705 1400 706 1403 707 1404 708 1418 709 1407 710 1402 711 1419 712 1422 713 1416 714 1429 715 1427 716 1435 717 1425 718 1444 719 1436 720 1414 721 1443 722 1432 723 1441 724 1437 725 1439 726 1447 727 1449 728 1446 729 1451 730 1453 731 1455 732 1457 733 1458 734 1460 735 1466 736 1461 737 1471 738 1469 739 1473 740 1470 741 1474 742 1480 743 1475 744 1476 745 1483 746 1482 747 1488 748 1478 749 1494 750 1491 751 1501 752 1493 753 1518 754 1492 755 1498 756 1500 757 1513 758 1509 759 1507 760 1510 761 1525 762 1524 763 1527 764 1516 765 1526 766 1520 767 1533 768 1536 769 1531 770 1532 771 1540 772 1539 773 1542 774 1544 775 1546 776 1550 777 1549 778 1553 779 1556 780 1537 781 1558 782 1557 783 1572 784 1568 785 1564 786 1567 787 1575 788 1571 789 1582 790 1551 791 1587 792 1578 793 1579 794 1569 795 1585 796 1590 797 1588 798 1584 799 1598 800 1591 801 1592 802 1589 803 1596 804 1606 805 1594 806 1605 807 1607 808 1612 809 1610 810 1614 811 1595 812 1609 813 1622 814 1616 815 1620 816 1623 817 1639 818 1625 819 1629 820 1641 821 1642 822 1644 823 1645 824 1626 825 1650 826 1651 827 1633 828 1646 829 1653 830 1649 831 1658 832 1662 833 1652 834 1654 835 1659 836 1665 837 1669 838 1668 839 1672 840 1671 841 1670 842 1674 843 1673 844 1680 845 1676 846 1675 847 1691 848 1694 849 1681 850 1712 851 1686 852 1697 853 1700 854 1704 855 1703 856 1706 857 1695 858 1716 859 1717 860 1719 861 1707 862 1720 863 1723 864 1714 865 1724 866 1728 867 1721 868 1729 869 1730 870 1737 871 1736 872 1738 873 1739 874 1742 875 1741 876 1747 877 1749 878 1752 879 1751 880 1753 881 1758 882 1759 883 1740 884 1770 885 1762 886 1761 887 1774 888 1772 889 1767 890 1771 891 1773 892 1775 893 1776 894 1778 895 1780 896 1779 897 1782 898 1789 899 1790 900 1796 901 1797 902 1800 903 1802 904 1799 905 1777 906 1805 907 1807 908 1820 909 1803 910 1814 911 1832 912 1819 913 1822 914 1816 915 1829 916 1825 917 1833 918 1824 919 1838 920 1826 921 1834 922 1839 923 1844 924 1831 925 1845 926 1865 927 1851 928 1853 929 1842 930 1854 931 1861 932 1856 933 1868 934 1850 935 1871 936 1870 937 1864 938 1881 939 1874 940 1872 941 1884 942 1880 943 1883 944 1877 945 1882 946 1892 947 1885 948 1890 949 1893 950 1897 951 1900 952 1899 953 1901 954 1903 955 1904 956 1906 957 1911 958 1907 959 1908 960 1913 961 1917 962 1916 963 1918 964 1922 965 1914 966 1933 967 1932 968 1928 969 1920 970 1936 971 1938 972 1939 973 1942 974 1930 975 1941 976 1943 977 1947 978 1951 979 1948 980 1953 981 1952 982 1958 983 1956 984 1959 985 1960 986 1965 987 1968 988 1962 989 1969 990 1977 991 1970 992 1979 993 1978 994 1975 995 1981 996 1982 997 1986 998 1980 999 1987 1000 1989