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