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