1 0 2 1 3 2 4 3 5 5 6 7 7 8 8 10 9 10 10 14 11 15 12 17 13 19 14 21 15 22 16 24 17 26 18 30 19 30 20 33 21 34 22 39 23 36 24 44 25 41 26 47 27 44 28 52 29 49 30 57 31 54 32 59 33 58 34 66 35 59 36 66 37 69 38 73 39 71 40 80 41 75 42 85 43 79 44 88 45 80 46 95 47 82 48 98 49 91 50 100 51 98 52 110 53 100 54 112 55 104 56 118 57 113 58 125 59 109 60 133 61 121 62 130 63 115 64 136 65 126 66 147 67 131 68 147 69 138 70 152 71 135 72 159 73 146 74 162 75 145 76 171 77 148 78 175 79 158 80 171 81 161 82 183 83 158 84 196 85 175 86 192 87 177 88 202 89 178 90 199 91 185 92 208 93 195 94 211 95 185 96 223 97 203 98 213 99 199 100 229 101 200 102 241 103 207 104 242 105 224 106 250 107 212 108 251 109 232 110 247 111 233 112 257 113 234 114 274 115 236 116 275 117 236 118 273 119 234 120 299 121 258 122 280 123 261 124 303 125 249 126 292 127 265 128 297 129 282 130 310 131 264 132 321 133 282 134 314 135 281 136 332 137 286 138 333 139 291 140 336 141 311 142 338 143 284 144 334 145 313 146 345 147 312 148 370 149 314 150 358 151 321 152 367 153 328 154 370 155 321 156 398 157 336 158 376 159 346 160 386 161 339 162 389 163 350 164 403 165 367 166 400 167 338 168 432 169 375 170 412 171 363 172 435 173 359 174 435 175 361 176 427 177 403 178 432 179 379 180 447 181 396 182 431 183 406 184 470 185 397 186 472 187 395 188 464 189 410 190 467 191 400 192 484 193 431 194 468 195 429 196 491 197 418 198 487 199 430 200 491 201 465 202 497 203 422 204 544 205 456 206 498 207 453 208 517 209 449 210 539 211 462 212 542 213 479 214 534 215 448 216 551 217 483 218 543 219 501 220 569 221 474 222 563 223 476 224 554 225 491 226 573 227 474 228 610 229 511 230 557 231 519 232 609 233 508 234 589 235 519 236 597 237 539 238 585 239 504 240 636 241 544 242 597 243 528 244 640 245 523 246 646 247 538 248 634 249 580 250 606 251 537 252 649 253 560 254 636 255 577 256 653 257 564 258 670 259 573 260 679 261 589 262 655 263 564 264 717 265 603 266 660 267 615 268 713 269 585 270 695 271 597 272 681 273 638 274 703 275 576 276 751 277 625 278 687 279 616 280 746 281 626 282 747 283 616 284 746 285 659 286 712 287 613 288 739 289 664 290 733 291 683 292 769 293 629 294 759 295 662 296 782 297 672 298 766 299 638 300 800 301 686 302 758 303 693 304 785 305 688 306 786 307 674 308 802 309 732 310 795 311 668 312 862 313 713 314 784 315 714 316 852 317 698 318 832 319 717 320 807 321 760 322 823 323 703 324 859 325 710 326 830 327 749 328 874 329 731 330 885 331 749 332 867 333 762 334 854 335 730 336 916 337 777 338 859 339 789 340 926 341 745 342 885 343 740 344 922 345 837 346 892 347 758 348 967 349 791 350 866 351 793 352 924 353 786 354 966 355 800 356 942 357 832 358 919 359 783 360 973 361 847 362 917 363 838 364 990 365 817 366 993 367 810 368 967 369 860 370 958 371 812 372 1059 373 854 374 941 375 867 376 1022 377 836 378 993 379 862 380 1020 381 902 382 983 383 831 384 1043 385 892 386 1004 387 892 388 1050 389 878 390 1051 391 874 392 1024 393 941 394 1036 395 868 396 1077 397 899 398 1008 399 944 400 1043 401 914 402 1083 403 909 404 1086 405 936 406 1047 407 890 408 1165 409 951 410 1075 411 970 412 1118 413 915 414 1098 415 948 416 1087 417 1015 418 1075 419 924 420 1196 421 984 422 1090 423 967 424 1176 425 937 426 1162 427 963 428 1158 429 1020 430 1115 431 948 432 1148 433 1008 434 1121 435 1042 436 1211 437 953 438 1203 439 989 440 1192 441 1024 442 1151 443 996 444 1264 445 1044 446 1138 447 1044 448 1179 449 1029 450 1184 451 1021 452 1240 453 1078 454 1182 455 1019 456 1314 457 1064 458 1176 459 1071 460 1264 461 1030 462 1256 463 1058 464 1238 465 1135 466 1240 467 1033 468 1280 469 1085 470 1229 471 1132 472 1292 473 1076 474 1298 475 1046 476 1285 477 1123 478 1256 479 1036 480 1365 481 1127 482 1256 483 1139 484 1342 485 1117 486 1279 487 1102 488 1321 489 1206 490 1273 491 1098 492 1422 493 1124 494 1278 495 1154 496 1345 497 1122 498 1389 499 1160 500 1328 501 1208 502 1298 503 1104 504 1414 505 1202 506 1326 507 1200 508 1418 509 1144 510 1403 511 1173 512 1355 513 1213 514 1359 515 1170 516 1490 517 1179 518 1350 519 1253 520 1467 521 1183 522 1418 523 1180 524 1431 525 1242 526 1397 527 1167 528 1476 529 1264 530 1395 531 1253 532 1488 533 1205 534 1487 535 1226 536 1487 537 1311 538 1407 539 1177 540 1530 541 1276 542 1414 543 1317 544 1477 545 1259 546 1508 547 1257 548 1515 549 1298 550 1419 551 1215 552 1601 553 1303 554 1467 555 1359 556 1547 557 1258 558 1494 559 1270 560 1519 561 1389 562 1511 563 1250 564 1657 565 1326 566 1466 567 1306 568 1597 569 1309 570 1591 571 1323 572 1549 573 1374 574 1517 575 1265 576 1567 577 1350 578 1518 579 1395 580 1631 581 1327 582 1620 583 1330 584 1619 585 1422 586 1558 587 1322 588 1686 589 1384 590 1567 591 1411 592 1628 593 1352 594 1620 595 1384 596 1660 597 1465 598 1561 599 1357 600 1708 601 1426 602 1583 603 1438 604 1722 605 1366 606 1707 607 1373 608 1637 609 1506 610 1666 611 1376 612 1723 613 1427 614 1613 615 1493 616 1736 617 1430 618 1727 619 1430 620 1740 621 1479 622 1629 623 1395 624 1808 625 1465 626 1649 627 1524 628 1764 629 1420 630 1738 631 1469 632 1773 633 1565 634 1712 635 1437 636 1863 637 1447 638 1689 639 1528 640 1744 641 1493 642 1810 643 1474 644 1790 645 1598 646 1730 647 1452 648 1829 649 1531 650 1680 651 1591 652 1850 653 1502 654 1817 655 1529 656 1775 657 1582 658 1750 659 1497 660 1970 661 1556 662 1767 663 1586 664 1882 665 1559 666 1836 667 1534 668 1843 669 1655 670 1779 671 1500 672 1939 673 1601 674 1809 675 1570 676 1929 677 1524 678 1887 679 1576 680 1934 681 1702 682 1800 683 1553 684 1940 685 1624 686 1780 687 1679 688 1923 689 1580 690 1972 691 1605 692 1919 693 1664 694 1875 695 1599 696 2068 697 1658 698 1858 699 1697 700 1923 701 1611 702 1927 703 1598 704 1909 705 1774 706 1899 707 1604 708 2112 709 1684 710 1884 711 1695 712 2005 713 1635 714 2016 715 1678 716 2020 717 1734 718 1928 719 1620 720 2027 721 1731 722 1931 723 1780 724 2068 725 1639 726 2014 727 1672 728 2037 729 1774 730 1990 731 1663 732 2187 733 1695 734 1918 735 1771 736 2074 737 1714 738 2050 739 1733 740 2094 741 1826 742 1992 743 1681 744 2240 745 1794 746 2010 747 1781 748 2098 749 1730 750 2094 751 1761 752 2071 753 1884 754 2019 755 1731 756 2178 757 1786 758 2023 759 1842 760 2205 761 1759 762 2153 763 1784 764 2160 765 1871 766 2052 767 1739 768 2203 769 1837 770 2083 771 1917 772 2219 773 1762 774 2163 775 1755 776 2175 777 1932 778 2102 779 1777 780 2326 781 1858 782 2061 783 1862 784 2161 785 1874 786 2270 787 1798 788 2242 789 1936 790 2139 791 1789 792 2298 793 1893 794 2115 795 2004 796 2280 797 1824 798 2251 799 1857 800 2165 801 1964 802 2172 803 1819 804 2417 805 1924 806 2163 807 1986 808 2317 809 1901 810 2237 811 1878 812 2281 813 2013 814 2205 815 1873 816 2405 817 1937 818 2204 819 1984 820 2387 821 1901 822 2326 823 1923 824 2325 825 2006 826 2244 827 1882 828 2411 829 1970 830 2255 831 2043 832 2269 833 1884 834 2409 835 1974 836 2347 837 2023 838 2228 839 1891 840 2558 841 2048 842 2284 843 2052 844 2453 845 1951 846 2354 847 1946 848 2374 849 2148 850 2250 851 1963 852 2557 853 1980 854 2280 855 2081 856 2497 857 1987 858 2445 859 2015 860 2428 861 2151 862 2330 863 1981 864 2434 865 2111 866 2324 867 2133 868 2484 869 2018 870 2512 871 2014 872 2502 873 2138 874 2356 875 1996 876 2662 877 2060 878 2335 879 2148 880 2501 881 2056 882 2431 883 2087 884 2512 885 2242 886 2425 887 2009 888 2662 889 2158 890 2439 891 2131 892 2547 893 2061 894 2544 895 2103 896 2467 897 2242 898 2463 899 2052 900 2587 901 2125 902 2395 903 2241 904 2639 905 2167 906 2593 907 2132 908 2552 909 2223 910 2489 911 2089 912 2702 913 2174 914 2497 915 2277 916 2654 917 2132 918 2581 919 2174 920 2629 921 2348 922 2486 923 2099 924 2787 925 2175 926 2502 927 2248 928 2629 929 2174 930 2683 931 2139 932 2680 933 2325 934 2515 935 2177 936 2755 937 2230 938 2540 939 2360 940 2754 941 2160 942 2698 943 2159 944 2631 945 2360 946 2604 947 2188 948 2868 949 2278 950 2500 951 2350 952 2749 953 2227 954 2692 955 2268 956 2732 957 2358 958 2556 959 2193 960 2851 961 2352 962 2593 963 2343 964 2784 965 2268 966 2780 967 2266 968 2763 969 2432 970 2690 971 2234 972 2801 973 2299 974 2624 975 2378 976 2765 977 2297 978 2816 979 2295 980 2774 981 2411 982 2676 983 2242 984 3040 985 2399 986 2627 987 2447 988 2856 989 2304 990 2796 991 2353 992 2756 993 2499 994 2730 995 2352 996 3037 997 2338 998 2703 999 2418 1000 2816