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