1 0 2 1 3 1 4 0 5 2 6 0 7 1 8 1 9 0 10 1 11 1 12 0 13 1 14 1 15 0 16 2 17 0 18 1 19 1 20 0 21 1 22 0 23 1 24 0 25 1 26 1 27 0 28 2 29 1 30 1 31 2 32 1 33 1 34 3 35 0 36 2 37 2 38 0 39 3 40 1 41 2 42 2 43 2 44 2 45 2 46 2 47 1 48 2 49 1 50 1 51 1 52 2 53 1 54 2 55 3 56 1 57 4 58 2 59 2 60 3 61 1 62 2 63 2 64 2 65 1 66 3 67 2 68 2 69 4 70 2 71 3 72 3 73 2 74 2 75 3 76 1 77 2 78 3 79 1 80 3 81 3 82 2 83 4 84 3 85 3 86 4 87 3 88 3 89 4 90 3 91 3 92 4 93 3 94 5 95 3 96 5 97 4 98 4 99 5 100 3 101 4 102 3 103 3 104 3 105 4 106 2 107 4 108 4 109 3 110 5 111 3 112 5 113 4 114 4 115 5 116 3 117 6 118 4 119 5 120 6 121 4 122 6 123 7 124 5 125 6 126 7 127 4 128 8 129 5 130 5 131 8 132 4 133 7 134 6 135 5 136 7 137 5 138 7 139 6 140 5 141 8 142 6 143 6 144 8 145 5 146 8 147 9 148 4 149 10 150 6 151 6 152 10 153 6 154 8 155 8 156 8 157 8 158 9 159 8 160 8 161 9 162 8 163 7 164 9 165 9 166 6 167 11 168 8 169 7 170 13 171 6 172 11 173 11 174 7 175 12 176 10 177 9 178 10 179 12 180 8 181 12 182 11 183 10 184 13 185 10 186 12 187 11 188 13 189 9 190 12 191 12 192 8 193 14 194 10 195 11 196 13 197 11 198 13 199 13 200 12 201 13 202 15 203 11 204 14 205 13 206 13 207 16 208 12 209 17 210 13 211 16 212 16 213 15 214 17 215 14 216 17 217 16 218 15 219 15 220 17 221 14 222 17 223 15 224 14 225 21 226 11 227 20 228 17 229 13 230 22 231 14 232 18 233 18 234 16 235 18 236 22 237 15 238 20 239 22 240 16 241 24 242 18 243 22 244 21 245 20 246 23 247 18 248 25 249 19 250 22 251 25 252 17 253 24 254 25 255 19 256 25 257 24 258 19 259 29 260 21 261 22 262 30 263 18 264 27 265 26 266 22 267 29 268 24 269 28 270 27 271 26 272 29 273 28 274 27 275 29 276 26 277 31 278 29 279 25 280 34 281 26 282 30 283 33 284 27 285 35 286 29 287 32 288 34 289 30 290 34 291 33 292 34 293 33 294 34 295 34 296 39 297 33 298 37 299 38 300 33 301 41 302 33 303 40 304 37 305 35 306 42 307 35 308 41 309 38 310 40 311 41 312 38 313 39 314 43 315 40 316 38 317 45 318 37 319 46 320 43 321 41 322 50 323 40 324 48 325 47 326 46 327 48 328 45 329 51 330 46 331 47 332 51 333 49 334 48 335 53 336 46 337 54 338 56 339 43 340 60 341 47 342 48 343 58 344 47 345 55 346 51 347 54 348 55 349 56 350 55 351 56 352 58 353 55 354 55 355 56 356 63 357 49 358 64 359 60 360 52 361 73 362 54 363 65 364 68 365 55 366 69 367 67 368 58 369 66 370 69 371 59 372 72 373 64 374 68 375 74 376 63 377 76 378 66 379 75 380 71 381 69 382 78 383 63 384 75 385 75 386 71 387 74 388 76 389 73 390 81 391 76 392 75 393 87 394 69 395 85 396 77 397 77 398 89 399 70 400 91 401 80 402 78 403 92 404 84 405 84 406 90 407 85 408 87 409 97 410 78 411 96 412 91 413 85 414 97 415 89 416 99 417 88 418 101 419 97 420 91 421 108 422 91 423 103 424 102 425 92 426 103 427 109 428 92 429 105 430 110 431 92 432 117 433 102 434 107 435 114 436 102 437 113 438 108 439 113 440 107 441 113 442 117 443 104 444 118 445 121 446 113 447 121 448 125 449 113 450 134 451 121 452 116 453 141 454 110 455 129 456 132 457 120 458 135 459 126 460 136 461 131 462 133 463 136 464 137 465 134 466 135 467 133 468 138 469 144 470 123 471 152 472 135 473 135 474 157 475 134 476 155 477 144 478 146 479 155 480 145 481 151 482 151 483 156 484 150 485 155 486 154 487 169 488 152 489 163 490 171 491 148 492 180 493 156 494 166 495 175 496 152 497 177 498 172 499 164 500 176 501 178 502 171 503 180 504 172 505 180 506 187 507 166 508 193 509 174 510 187 511 191 512 177 513 202 514 178 515 192 516 199 517 193 518 193 519 196 520 200 521 197 522 201 523 198 524 211 525 197 526 210 527 205 528 206 529 226 530 190 531 230 532 212 533 199 534 236 535 210 536 221 537 226 538 219 539 226 540 238 541 216 542 235 543 242 544 216 545 244 546 230 547 243 548 234 549 241 550 249 551 231 552 261 553 237 554 253 555 256 556 233 557 260 558 260 559 242 560 260 561 268 562 246 563 278 564 257 565 267 566 286 567 249 568 288 569 267 570 276 571 283 572 273 573 293 574 272 575 287 576 296 577 293 578 288 579 300 580 291 581 302 582 299 583 287 584 322 585 281 586 310 587 309 588 295 589 331 590 291 591 326 592 317 593 300 594 330 595 324 596 313 597 325 598 327 599 318 600 353 601 314 602 341 603 353 604 320 605 360 606 340 607 354 608 344 609 351 610 362 611 341 612 368 613 356 614 364 615 370 616 356 617 365 618 391 619 360 620 366 621 401 622 348 623 396 624 384 625 370 626 409 627 370 628 399 629 403 630 394 631 401 632 409 633 407 634 400 635 406 636 416 637 422 638 398 639 434 640 410 641 425 642 443 643 403 644 460 645 417 646 429 647 455 648 432 649 445 650 440 651 458 652 444 653 456 654 454 655 471 656 463 657 462 658 476 659 463 660 502 661 451 662 498 663 492 664 457 665 519 666 479 667 502 668 498 669 493 670 513 671 506 672 502 673 515 674 524 675 501 676 525 677 509 678 539 679 525 680 511 681 564 682 508 683 555 684 551 685 540 686 569 687 539 688 566 689 574 690 563 691 563 692 587 693 572 694 579 695 577 696 593 697 607 698 567 699 628 700 585 701 604 702 634 703 575 704 645 705 601 706 597 707 647 708 625 709 608 710 646 711 640 712 627 713 667 714 627 715 672 716 658 717 647 718 673 719 656 720 694 721 642 722 703 723 686 724 652 725 728 726 689 727 698 728 715 729 699 730 707 731 746 732 685 733 724 734 760 735 680 736 760 737 733 738 735 739 765 740 740 741 773 742 752 743 771 744 764 745 787 746 775 747 760 748 790 749 801 750 788 751 789 752 830 753 787 754 829 755 818 756 809 757 863 758 790 759 849 760 844 761 819 762 860 763 843 764 861 765 855 766 857 767 873 768 908 769 852 770 894 771 903 772 871 773 924 774 878 775 929 776 908 777 907 778 942 779 922 780 957 781 922 782 970 783 958 784 931 785 973 786 977 787 961 788 969 789 985 790 960 791 1029 792 968 793 996 794 1049 795 960 796 1042 797 1024 798 1019 799 1037 800 1027 801 1055 802 1039 803 1053 804 1058 805 1083 806 1069 807 1071 808 1077 809 1119 810 1098 811 1077 812 1158 813 1077 814 1131 815 1147 816 1104 817 1179 818 1114 819 1153 820 1181 821 1149 822 1162 823 1193 824 1179 825 1174 826 1190 827 1188 828 1238 829 1178 830 1226 831 1227 832 1206 833 1267 834 1208 835 1281 836 1244 837 1233 838 1303 839 1265 840 1281 841 1285 842 1306 843 1300 844 1310 845 1294 846 1351 847 1332 848 1303 849 1375 850 1314 851 1387 852 1354 853 1358 854 1417 855 1339 856 1405 857 1414 858 1403 859 1402 860 1421 861 1430 862 1438 863 1433 864 1443 865 1490 866 1441 867 1481 868 1471 869 1498 870 1520 871 1459 872 1556 873 1491 874 1499 875 1565 876 1525 877 1550 878 1544 879 1555 880 1581 881 1603 882 1545 883 1619 884 1616 885 1573 886 1631 887 1615 888 1653 889 1615 890 1665 891 1661 892 1645 893 1712 894 1653 895 1732 896 1699 897 1670 898 1752 899 1750 900 1704 901 1750 902 1780 903 1723 904 1810 905 1751 906 1798 907 1831 908 1757 909 1843 910 1817 911 1835 912 1829 913 1862 914 1871 915 1824 916 1890 917 1892 918 1904 919 1890 920 1914 921 1918 922 1959 923 1924 924 1939 925 2018 926 1913 927 2003 928 1995 929 1989 930 2045 931 1986 932 2070 933 2037 934 2027 935 2081 936 2094 937 2075 938 2083 939 2102 940 2123 941 2158 942 2088 943 2186 944 2157 945 2139 946 2202 947 2166 948 2235 949 2172 950 2225 951 2256 952 2204 953 2274 954 2257 955 2295 956 2284 957 2267 958 2309 959 2371 960 2291 961 2324 962 2400 963 2300 964 2417 965 2374 966 2394 967 2448 968 2379 969 2459 970 2463 971 2454 972 2450 973 2515 974 2498 975 2469 976 2516 977 2542 978 2559 979 2528 980 2587 981 2558 982 2624 983 2608 984 2583 985 2703 986 2581 987 2639 988 2711 989 2652 990 2689 991 2711 992 2722 993 2737 994 2746 995 2726 996 2832 997 2775 998 2757 999 2829 1000 2806