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