0 0 1 0 2 1 3 1 4 1 5 1 6 2 7 2 8 0 9 2 10 3 11 6 12 3 13 2 14 2 15 5 16 7 17 10 18 8 19 9 20 5 21 5 22 9 23 15 24 10 25 8 26 4 27 5 28 15 29 27 30 15 31 17 32 15 33 20 34 25 35 18 36 19 37 18 38 14 39 21 40 21 41 27 42 22 43 19 44 22 45 22 46 28 47 31 48 29 49 25 50 22 51 27 52 35 53 43 54 35 55 34 56 27 57 42 58 40 59 46 60 45 61 53 62 36 63 33 64 48 65 46 66 53 67 34 68 39 69 57 70 53 71 50 72 47 73 39 74 63 75 66 76 60 77 60 78 55 79 58 80 69 81 78 82 81 83 60 84 66 85 70 86 62 87 68 88 73 89 84 90 77 91 79 92 80 93 80 94 78 95 98 96 90 97 75 98 87 99 83 100 113 101 105 102 106 103 93 104 104 105 103 106 112 107 102 108 101 109 103 110 97 111 125 112 110 113 121 114 105 115 104 116 117 117 127 118 111 119 108 120 108 121 109 122 119 123 130 124 128 125 149 126 134 127 130 128 148 129 145 130 147 131 124 132 140 133 137 134 159 135 155 136 169 137 133 138 142 139 162 140 191 141 187 142 189 143 152 144 146 145 162 146 173 147 203 148 197 149 163 150 160 151 172 152 176 153 189 154 191 155 174 156 205 157 185 158 191 159 179 160 207 161 193 162 207 163 219 164 212 165 231 166 213 167 214 168 214 169 215 170 231 171 230 172 220 173 214 174 222 175 221 176 220 177 220 178 242 179 224 180 243 181 233 182 236 183 255 184 257 185 284 186 225 187 251 188 257 189 260 190 259 191 273 192 268 193 276 194 253 195 236 196 271 197 275 198 258 199 260 200 272 201 253 202 289 203 265 204 311 205 279 206 316 207 311 208 295 209 299 210 316 211 315 212 310 213 297 214 274 215 284 216 297 217 309 218 349 219 343 220 324 221 313 222 330 223 329 224 372 225 305 226 340 227 329 228 366 229 335 230 359 231 355 232 372 233 353 234 342 235 378 236 342 237 386 238 394 239 375 240 419 241 368 242 370 243 406 244 411 245 405 246 431 247 382 248 399 249 376 250 425 251 395 252 399 253 440 254 413 255 448 256 401 257 436 258 412 259 444 260 410 261 411 262 427 263 444 264 423 265 463 266 420 267 465 268 476 269 469 270 436 271 468 272 499 273 497 274 463 275 468 276 475 277 483 278 498 279 510 280 514 281 518 282 499 283 497 284 453 285 471 286 508 287 544 288 508 289 521 290 516 291 504 292 496 293 524 294 519 295 527 296 515 297 559 298 532 299 537 300 537 301 516 302 589 303 557 304 573 305 522 306 524 307 571 308 547 309 563 310 574 311 584 312 578 313 580 314 591 315 598 316 572 317 557 318 595 319 612 320 626 321 614 322 590 323 614 324 627 325 617 326 632 327 628 328 628 329 649 330 654 331 671 332 641 333 633 334 628 335 640 336 653 337 647 338 668 339 668 340 644 341 645 342 701 343 704 344 669 345 625 346 690 347 689 348 685 349 708 350 667 351 671 352 650 353 772 354 732 355 664 356 658 357 719 358 723 359 731 360 745 361 710 362 692 363 705 364 748 365 707 366 757 367 746 368 741 369 741 370 768 371 809 372 758 373 741 374 759 375 770 376 814 377 796 378 775 379 779 380 786 381 818 382 787 383 819 384 834 385 780 386 841 387 821 388 806 389 841 390 813 391 799 392 883 393 838 394 863 395 838 396 825 397 795 398 868 399 886 400 881 401 861 402 870 403 896 404 870 405 877 406 892 407 867 408 915 409 923 410 902 411 888 412 931 413 965 414 933 415 922 416 895 417 914 418 954 419 927 420 951 421 928 422 979 423 918 424 914 425 967 426 1000 427 944 428 930 429 969 430 986 431 1020 432 1013 433 1015 434 979 435 988 436 1044 437 982 438 943 439 1053 440 1005 441 1057 442 996 443 1040 444 1009 445 1049 446 1020 447 1066 448 1069 449 1061 450 1090 451 1044 452 1011 453 1032 454 1044 455 1091 456 1094 457 1086 458 1037 459 1088 460 1085 461 1108 462 1087 463 1081 464 1101 465 1122 466 1144 467 1118 468 1174 469 1140 470 1070 471 1102 472 1121 473 1138 474 1143 475 1171 476 1136 477 1197 478 1140 479 1126 480 1178 481 1184 482 1103 483 1162 484 1188 485 1178 486 1168 487 1209 488 1237 489 1151 490 1225 491 1152 492 1205 493 1238 494 1262 495 1209 496 1200 497 1254 498 1169 499 1252 500 1273 501 1232 502 1246 503 1270 504 1289 505 1359 506 1253 507 1325 508 1243 509 1258 510 1293 511 1321 512 1257 513 1252 514 1339 515 1337 516 1335 517 1333 518 1301 519 1287 520 1344 521 1315 522 1364 523 1353 524 1293 525 1377 526 1339 527 1386 528 1397 529 1360 530 1342 531 1362 532 1418 533 1387 534 1454 535 1398 536 1424 537 1356 538 1394 539 1364 540 1471 541 1403 542 1377 543 1501 544 1454 545 1498 546 1530 547 1392 548 1450 549 1489 550 1485 551 1466 552 1550 553 1541 554 1515 555 1477 556 1474 557 1523 558 1476 559 1474 560 1491 561 1537 562 1552 563 1453 564 1460 565 1592 566 1598 567 1527 568 1550 569 1582 570 1613 571 1572 572 1626 573 1611 574 1527 575 1559 576 1560 577 1659 578 1579 579 1645 580 1619 581 1599 582 1667 583 1706 584 1647 585 1664 586 1651 587 1632 588 1629 589 1674 590 1617 591 1708 592 1687 593 1685 594 1618 595 1603 596 1636 597 1756 598 1784 599 1751 600 1665 601 1727 602 1738 603 1774 604 1680 605 1655 606 1754 607 1726 608 1728 609 1703 610 1746 611 1742 612 1783 613 1767 614 1762 615 1785 616 1749 617 1777 618 1864 619 1814 620 1818 621 1804 622 1760 623 1807 624 1833 625 1840 626 1930 627 1800 628 1869 629 1822 630 1947 631 1850 632 1844 633 1864 634 1821 635 1814 636 1878 637 1912 638 1920 639 1956 640 1833 641 1872 642 1915 643 1873 644 1940 645 1936 646 1926 647 1917 648 1824 649 1956 650 1949 651 1914 652 1956 653 2055 654 2034 655 2013 656 2007 657 1982 658 1966 659 1993 660 1982 661 1983 662 2041 663 2055 664 2039 665 2051 666 2050 667 1951 668 2102 669 2063 670 2131 671 2081 672 2085 673 2068 674 2018 675 2094 676 2063 677 2046 678 2075 679 2041 680 2161 681 2074 682 2161 683 2126 684 2100 685 2152 686 2119 687 2150 688 2096 689 2139 690 2201 691 2098 692 2166 693 2151 694 2184 695 2169 696 2189 697 2138 698 2186 699 2262 700 2164 701 2296 702 2248 703 2168 704 2219 705 2152 706 2313 707 2200 708 2195 709 2249 710 2225 711 2264 712 2238 713 2309 714 2278 715 2302 716 2326 717 2164 718 2264 719 2355 720 2349 721 2331 722 2268 723 2340 724 2325 725 2443 726 2350 727 2300 728 2315 729 2382 730 2398 731 2347 732 2416 733 2307 734 2450 735 2506 736 2526 737 2391 738 2399 739 2364 740 2491 741 2524 742 2503 743 2344 744 2521 745 2385 746 2406 747 2493 748 2578 749 2490 750 2526 751 2512 752 2391 753 2546 754 2457 755 2463 756 2504 757 2395 758 2538 759 2633 760 2517 761 2467 762 2598 763 2574 764 2463 765 2578 766 2539 767 2585 768 2641 769 2626 770 2694 771 2510 772 2650 773 2554 774 2680 775 2558 776 2717 777 2543 778 2611 779 2729 780 2607 781 2719 782 2668 783 2611 784 2737 785 2565 786 2618 787 2781 788 2679 789 2705 790 2729 791 2622 792 2735 793 2731 794 2774 795 2737 796 2626 797 2717 798 2734 799 2772 800 2789 801 2772 802 2736 803 2762 804 2793 805 2700 806 2797 807 2709 808 2774 809 2846 810 2863 811 2846 812 2786 813 2778 814 2895 815 2700 816 2868 817 2754 818 2787 819 3005 820 2920 821 2769 822 2867 823 2938 824 2831 825 2951 826 2983 827 2913 828 2925 829 2945 830 3013 831 2952 832 2893 833 2908 834 2921 835 2935 836 3006 837 3025 838 2940 839 2938 840 3005 841 3024 842 2943 843 2955 844 2839 845 3073 846 2978 847 3009 848 3076 849 3054 850 2992 851 3024 852 3021 853 3029 854 3095 855 3194 856 3044 857 3145 858 3104 859 3177 860 3097 861 3145 862 3180 863 3146 864 3124 865 3178 866 3107 867 3060 868 3128 869 3255 870 3141 871 3163 872 3203 873 3215 874 3221 875 3182 876 3234 877 3205 878 3199 879 3331 880 3268 881 3244 882 3360 883 3161 884 3322 885 3263 886 3289 887 3291 888 3310 889 3306 890 3353 891 3277 892 3353 893 3341 894 3269 895 3299 896 3279 897 3449 898 3228 899 3419 900 3435 901 3396 902 3354 903 3397 904 3358 905 3374 906 3286 907 3600 908 3427 909 3443 910 3481 911 3463 912 3448 913 3632 914 3422 915 3454 916 3527 917 3446 918 3434 919 3616 920 3551 921 3536 922 3458 923 3409 924 3564 925 3522 926 3523 927 3661 928 3459 929 3509 930 3577 931 3553 932 3483 933 3663 934 3485 935 3488 936 3587 937 3557 938 3524 939 3565 940 3564 941 3580 942 3680 943 3604 944 3621 945 3673 946 3669 947 3757 948 3666 949 3685 950 3710 951 3745 952 3677 953 3671 954 3740 955 3645 956 3701 957 3651 958 3679 959 3720 960 3726 961 3713 962 3784 963 3741 964 3831 965 3865 966 3714 967 3742 968 3955 969 3707 970 3861 971 3664 972 3777 973 3770 974 3841 975 3845 976 3957 977 3900 978 3946 979 3778 980 3920 981 3953 982 3820 983 3972 984 3933 985 3895 986 3891 987 4016 988 4002 989 3994 990 3961 991 3958 992 3973 993 4005 994 3892 995 4054 996 4083 997 3977 998 4009 999 4082 1000 3994