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