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