1 0 2 1 3 2 4 3 5 4 6 5 7 7 8 8 9 10 10 14 11 15 12 16 13 17 14 18 15 19 16 21 17 27 18 32 19 36 20 38 21 41 22 43 23 45 24 47 25 48 26 49 27 50 28 51 29 54 30 60 31 61 32 62 33 66 34 67 35 68 36 69 37 70 38 71 39 76 40 77 41 79 42 83 43 85 44 88 45 90 46 92 47 93 48 94 49 95 50 96 51 98 52 100 53 102 54 105 55 106 56 107 57 113 58 116 59 118 60 121 61 122 62 124 63 125 64 127 65 128 66 129 67 132 68 133 69 136 70 142 71 144 72 150 73 151 74 153 75 154 76 155 77 157 78 159 79 160 80 162 81 167 82 171 83 173 84 176 85 180 86 184 87 189 88 191 89 193 90 198 91 200 92 201 93 202 94 203 95 204 96 205 97 212 98 214 99 222 100 230 101 231 102 232 103 235 104 237 105 238 106 242 107 243 108 246 109 254 110 256 111 258 112 259 113 263 114 265 115 269 116 270 117 271 118 276 119 278 120 279 121 281 122 282 123 283 124 285 125 288 126 289 127 290 128 292 129 293 130 297 131 304 132 305 133 307 134 308 135 311 136 316 137 319 138 320 139 323 140 324 141 326 142 327 143 330 144 336 145 337 146 340 147 343 148 344 149 346 150 347 151 349 152 353 153 354 154 358 155 359 156 363 157 366 158 370 159 374 160 378 161 380 162 382 163 385 164 387 165 389 166 395 167 397 168 401 169 409 170 410 171 411 172 412 173 413 174 417 175 418 176 419 177 421 178 423 179 430 180 431 181 434 182 436 183 439 184 440 185 441 186 444 187 445 188 450 189 451 190 452 191 453 192 456 193 461 194 464 195 470 196 472 197 477 198 478 199 484 200 485 201 490 202 491 203 492 204 495 205 496 206 497 207 498 208 499 209 506 210 508 211 509 212 511 213 518 214 521 215 523 216 529 217 532 218 534 219 535 220 536 221 541 222 543 223 547 224 549 225 550 226 552 227 558 228 562 229 564 230 566 231 567 232 568 233 569 234 571 235 575 236 583 237 584 238 588 239 591 240 593 241 594 242 597 243 599 244 600 245 601 246 602 247 610 248 618 249 619 250 621 251 622 252 623 253 628 254 629 255 630 256 631 257 634 258 638 259 643 260 645 261 648 262 649 263 653 264 654 265 657 266 659 267 662 268 665 269 677 270 683 271 684 272 686 273 693 274 694 275 695 276 696 277 697 278 704 279 705 280 707 281 708 282 710 283 711 284 712 285 714 286 716 287 717 288 720 289 721 290 730 291 731 292 732 293 734 294 736 295 739 296 740 297 742 298 744 299 749 300 750 301 752 302 753 303 755 304 758 305 759 306 762 307 763 308 764 309 765 310 769 311 771 312 773 313 774 314 776 315 778 316 781 317 782 318 783 319 784 320 789 321 796 322 798 323 800 324 802 325 803 326 805 327 807 328 808 329 814 330 815 331 817 332 818 333 820 334 821 335 822 336 824 337 825 338 826 339 827 340 833 341 836 342 837 343 838 344 840 345 843 346 847 347 848 348 850 349 852 350 853 351 855 352 863 353 866 354 869 355 870 356 873 357 875 358 876 359 882 360 887 361 891 362 895 363 901 364 902 365 903 366 904 367 905 368 912 369 914 370 916 371 917 372 919 373 921 374 925 375 927 376 929 377 932 378 938 379 939 380 943 381 945 382 946 383 952 384 957 385 958 386 959 387 961 388 963 389 968 390 970 391 972 392 976 393 979 394 982 395 986 396 992 397 995 398 996 399 1003 400 1004 401 1005 402 1008 403 1019 404 1020 405 1028 406 1029 407 1031 408 1035 409 1036 410 1041 411 1042 412 1045 413 1050 414 1052 415 1056 416 1058 417 1059 418 1060 419 1061 420 1063 421 1072 422 1073 423 1077 424 1080 425 1082 426 1084 427 1090 428 1091 429 1094 430 1095 431 1097 432 1101 433 1102 434 1103 435 1110 436 1111 437 1113 438 1119 439 1124 440 1128 441 1130 442 1132 443 1135 444 1136 445 1141 446 1143 447 1147 448 1148 449 1149 450 1150 451 1156 452 1159 453 1160 454 1162 455 1163 456 1166 457 1167 458 1172 459 1173 460 1177 461 1178 462 1179 463 1180 464 1189 465 1191 466 1193 467 1194 468 1195 469 1200 470 1201 471 1205 472 1206 473 1221 474 1224 475 1225 476 1226 477 1228 478 1232 479 1237 480 1238 481 1240 482 1243 483 1245 484 1246 485 1249 486 1250 487 1251 488 1257 489 1259 490 1266 491 1267 492 1268 493 1272 494 1275 495 1280 496 1281 497 1286 498 1288 499 1290 500 1292 501 1294 502 1297 503 1302 504 1303 505 1308 506 1311 507 1316 508 1319 509 1320 510 1331 511 1341 512 1342 513 1344 514 1348 515 1349 516 1360 517 1361 518 1363 519 1364 520 1366 521 1369 522 1376 523 1379 524 1381 525 1382 526 1383 527 1394 528 1396 529 1399 530 1400 531 1401 532 1408 533 1409 534 1418 535 1420 536 1424 537 1426 538 1427 539 1432 540 1434 541 1435 542 1438 543 1442 544 1445 545 1449 546 1451 547 1452 548 1453 549 1454 550 1455 551 1458 552 1462 553 1463 554 1466 555 1468 556 1470 557 1471 558 1484 559 1486 560 1487 561 1489 562 1492 563 1493 564 1496 565 1500 566 1501 567 1503 568 1509 569 1511 570 1513 571 1518 572 1524 573 1530 574 1532 575 1536 576 1537 577 1540 578 1541 579 1546 580 1548 581 1550 582 1551 583 1553 584 1554 585 1555 586 1556 587 1557 588 1558 589 1561 590 1563 591 1567 592 1568 593 1569 594 1572 595 1577 596 1579 597 1587 598 1588 599 1592 600 1594 601 1595 602 1596 603 1597 604 1601 605 1603 606 1609 607 1611 608 1616 609 1617 610 1622 611 1632 612 1634 613 1645 614 1646 615 1649 616 1652 617 1653 618 1655 619 1656 620 1657 621 1665 622 1668 623 1669 624 1672 625 1673 626 1675 627 1680 628 1683 629 1684 630 1686 631 1689 632 1694 633 1696 634 1699 635 1706 636 1707 637 1709 638 1711 639 1715 640 1719 641 1720 642 1723 643 1724 644 1726 645 1730 646 1731 647 1738 648 1740 649 1745 650 1756 651 1762 652 1765 653 1766 654 1767 655 1775 656 1776 657 1777 658 1778 659 1783 660 1784 661 1787 662 1789 663 1795 664 1796 665 1798 666 1801 667 1806 668 1808 669 1809 670 1812 671 1816 672 1818 673 1819 674 1823 675 1827 676 1832 677 1834 678 1836 679 1837 680 1840 681 1844 682 1845 683 1852 684 1855 685 1856 686 1858 687 1864 688 1866 689 1869 690 1871 691 1878 692 1880 693 1881 694 1883 695 1889 696 1893 697 1894 698 1895 699 1902 700 1903 701 1904 702 1909 703 1910 704 1913 705 1914 706 1917 707 1919 708 1936 709 1938 710 1939 711 1942 712 1951 713 1952 714 1953 715 1954 716 1957 717 1958 718 1960 719 1961 720 1962 721 1965 722 1968 723 1970 724 1971 725 1974 726 1975 727 1979 728 1981 729 1983 730 1987 731 1988 732 1997 733 1999 734 2004 735 2006 736 2007 737 2010 738 2019 739 2021 740 2023 741 2026 742 2029 743 2038 744 2042 745 2043 746 2045 747 2046 748 2048 749 2049 750 2050 751 2051 752 2057 753 2060 754 2062 755 2064 756 2065 757 2068 758 2071 759 2073 760 2074 761 2075 762 2076 763 2084 764 2090 765 2091 766 2094 767 2097 768 2109 769 2112 770 2114 771 2118 772 2122 773 2124 774 2125 775 2126 776 2128 777 2133 778 2135 779 2138 780 2139 781 2142 782 2147 783 2148 784 2149 785 2151 786 2152 787 2156 788 2157 789 2161 790 2162 791 2164 792 2174 793 2175 794 2177 795 2178 796 2180 797 2185 798 2189 799 2190 800 2193 801 2199 802 2200 803 2203 804 2207 805 2208 806 2214 807 2215 808 2216 809 2221 810 2226 811 2228 812 2234 813 2235 814 2238 815 2240 816 2244 817 2246 818 2254 819 2263 820 2270 821 2274 822 2276 823 2279 824 2280 825 2281 826 2291 827 2294 828 2295 829 2298 830 2299 831 2302 832 2303 833 2304 834 2310 835 2315 836 2317 837 2320 838 2321 839 2323 840 2325 841 2326 842 2328 843 2332 844 2333 845 2336 846 2337 847 2338 848 2342 849 2344 850 2345 851 2346 852 2347 853 2348 854 2354 855 2355 856 2360 857 2364 858 2373 859 2376 860 2377 861 2382 862 2383 863 2388 864 2389 865 2393 866 2397 867 2398 868 2399 869 2404 870 2408 871 2410 872 2412 873 2413 874 2415 875 2420 876 2424 877 2425 878 2433 879 2434 880 2436 881 2446 882 2448 883 2450 884 2452 885 2453 886 2455 887 2456 888 2458 889 2463 890 2466 891 2467 892 2474 893 2478 894 2480 895 2481 896 2486 897 2487 898 2489 899 2492 900 2493 901 2498 902 2499 903 2500 904 2502 905 2505 906 2507 907 2512 908 2515 909 2516 910 2519 911 2520 912 2521 913 2529 914 2534 915 2537 916 2538 917 2540 918 2543 919 2544 920 2547 921 2549 922 2554 923 2555 924 2556 925 2559 926 2568 927 2569 928 2570 929 2573 930 2581 931 2589 932 2591 933 2593 934 2595 935 2603 936 2606 937 2607 938 2611 939 2612 940 2614 941 2615 942 2620 943 2623 944 2629 945 2631 946 2634 947 2635 948 2636 949 2642 950 2643 951 2644 952 2648 953 2650 954 2651 955 2663 956 2667 957 2668 958 2669 959 2673 960 2674 961 2676 962 2680 963 2689 964 2692 965 2696 966 2700 967 2706 968 2709 969 2711 970 2712 971 2716 972 2722 973 2724 974 2727 975 2731 976 2735 977 2739 978 2741 979 2747 980 2750 981 2754 982 2755 983 2760 984 2762 985 2765 986 2768 987 2775 988 2776 989 2779 990 2785 991 2786 992 2787 993 2788 994 2790 995 2791 996 2793 997 2796 998 2802 999 2805 1000 2806