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