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