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