0 1 1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 5 10 6 11 7 12 9 13 10 14 12 15 13 16 15 17 16 18 19 19 21 20 24 21 26 22 29 23 31 24 35 25 38 26 42 27 45 28 50 29 53 30 58 31 62 32 68 33 72 34 78 35 83 36 90 37 95 38 102 39 108 40 116 41 122 42 131 43 138 44 147 45 154 46 164 47 172 48 183 49 192 50 203 51 212 52 224 53 234 54 247 55 258 56 272 57 283 58 297 59 309 60 325 61 338 62 354 63 368 64 385 65 399 66 417 67 433 68 452 69 468 70 488 71 505 72 526 73 544 74 566 75 585 76 608 77 628 78 652 79 673 80 698 81 720 82 746 83 769 84 797 85 821 86 849 87 874 88 904 89 930 90 961 91 989 92 1021 93 1049 94 1082 95 1112 96 1147 97 1178 98 1214 99 1246 100 1283 101 1316 102 1355 103 1390 104 1430 105 1466 106 1507 107 1544 108 1587 109 1626 110 1670 111 1710 112 1756 113 1797 114 1844 115 1887 116 1936 117 1980 118 2030 119 2076 120 2128 121 2175 122 2228 123 2277 124 2332 125 2382 126 2439 127 2491 128 2549 129 2602 130 2662 131 2717 132 2779 133 2836 134 2899 135 2957 136 3022 137 3082 138 3149 139 3211 140 3280 141 3343 142 3413 143 3478 144 3551 145 3618 146 3692 147 3761 148 3837 149 3907 150 3985 151 4058 152 4138 153 4212 154 4294 155 4370 156 4454 157 4532 158 4618 159 4698 160 4786 161 4868 162 4958 163 5042 164 5134 165 5220 166 5314 167 5402 168 5499 169 5589 170 5687 171 5779 172 5880 173 5974 174 6077 175 6174 176 6279 177 6377 178 6484 179 6585 180 6695 181 6798 182 6910 183 7015 184 7129 185 7236 186 7353 187 7463 188 7582 189 7694 190 7815 191 7929 192 8053 193 8170 194 8296 195 8415 196 8544 197 8665 198 8796 199 8920 200 9054 201 9180 202 9316 203 9445 204 9584 205 9715 206 9856 207 9990 208 10134 209 10270 210 10417 211 10556 212 10705 213 10846 214 10998 215 11142 216 11297 217 11444 218 11601 219 11750 220 11910 221 12062 222 12225 223 12380 224 12546 225 12703 226 12871 227 13031 228 13203 229 13366 230 13540 231 13706 232 13883 233 14051 234 14231 235 14403 236 14586 237 14760 238 14946 239 15123 240 15312 241 15492 242 15684 243 15867 244 16062 245 16248 246 16446 247 16635 248 16836 249 17028 250 17232 251 17427 252 17635 253 17833 254 18043 255 18244 256 18458 257 18662 258 18879 259 19087 260 19307 261 19517 262 19740 263 19954 264 20181 265 20398 266 20628 267 20848 268 21081 269 21304 270 21541 271 21768 272 22008 273 22238 274 22481 275 22714 276 22961 277 23198 278 23448 279 23688 280 23942 281 24185 282 24442 283 24689 284 24950 285 25200 286 25464 287 25718 288 25986 289 26243 290 26514 291 26775 292 27050 293 27314 294 27593 295 27861 296 28143 297 28414 298 28700 299 28975 300 29265 301 29544 302 29837 303 30119 304 30416 305 30702 306 31003 307 31293 308 31598 309 31891 310 32199 311 32496 312 32809 313 33110 314 33426 315 33731 316 34051 317 34359 318 34683 319 34996 320 35324 321 35640 322 35972 323 36292 324 36628 325 36952 326 37292 327 37620 328 37964 329 38296 330 38644 331 38980 332 39332 333 39672 334 40028 335 40372 336 40733 337 41081 338 41445 339 41797 340 42166 341 42522 342 42895 343 43256 344 43633 345 43997 346 44378 347 44747 348 45133 349 45506 350 45896 351 46273 352 46667 353 47048 354 47447 355 47833 356 48236 357 48626 358 49033 359 49427 360 49839 361 50238 362 50654 363 51057 364 51478 365 51885 366 52310 367 52722 368 53152 369 53568 370 54002 371 54423 372 54862 373 55287 374 55730 375 56160 376 56608 377 57042 378 57495 379 57934 380 58391 381 58834 382 59296 383 59744 384 60211 385 60664 386 61135 387 61592 388 62068 389 62530 390 63011 391 63478 392 63964 393 64435 394 64925 395 65401 396 65897 397 66378 398 66878 399 67364 400 67869 401 68359 402 68869 403 69365 404 69880 405 70380 406 70900 407 71405 408 71930 409 72440 410 72970 411 73485 412 74020 413 74540 414 75080 415 75605 416 76150 417 76680 418 77230 419 77765 420 78321 421 78861 422 79421 423 79966 424 80532 425 81082 426 81653 427 82209 428 82785 429 83345 430 83926 431 84492 432 85079 433 85650 434 86242 435 86818 436 87415 437 87996 438 88599 439 89186 440 89794 441 90386 442 90999 443 91596 444 92215 445 92818 446 93442 447 94050 448 94680 449 95293 450 95928 451 96547 452 97188 453 97812 454 98458 455 99088 456 99740 457 100375 458 101032 459 101673 460 102336 461 102982 462 103651 463 104303 464 104977 465 105634 466 106314 467 106977 468 107663 469 108332 470 109023 471 109697 472 110394 473 111074 474 111777 475 112463 476 113172 477 113863 478 114577 479 115274 480 115995 481 116698 482 117424 483 118133 484 118865 485 119579 486 120317 487 121038 488 121782 489 122508 490 123258 491 123990 492 124746 493 125484 494 126246 495 126990 496 127758 497 128508 498 129282 499 130038 500 130818 501 131580 502 132366 503 133134 504 133927 505 134701 506 135499 507 136279 508 137084 509 137870 510 138681 511 139474 512 140291 513 141089 514 141912 515 142717 516 143547 517 144358 518 145194 519 146011 520 146853 521 147676 522 148525 523 149355 524 150210 525 151046 526 151907 527 152749 528 153617 529 154466 530 155340 531 156195 532 157076 533 157937 534 158824 535 159692 536 160586 537 161460 538 162360 539 163241 540 164148 541 165035 542 165948 543 166842 544 167762 545 168662 546 169589 547 170496 548 171429 549 172342 550 173282 551 174202 552 175149 553 176076 554 177029 555 177962 556 178922 557 179862 558 180829 559 181776 560 182750 561 183703 562 184683 563 185643 564 186631 565 187598 566 188592 567 189566 568 190567 569 191547 570 192555 571 193543 572 194558 573 195552 574 196574 575 197575 576 198604 577 199612 578 200648 579 201663 580 202706 581 203728 582 204778 583 205807 584 206864 585 207900 586 208964 587 210007 588 211079 589 212129 590 213207 591 214264 592 215350 593 216414 594 217507 595 218579 596 219679 597 220757 598 221864 599 222950 600 224065 601 225158 602 226280 603 227380 604 228509 605 229616 606 230753 607 231868 608 233012 609 234134 610 235285 611 236414 612 237573 613 238710 614 239876 615 241020 616 242194 617 243345 618 244526 619 245685 620 246874 621 248040 622 249236 623 250410 624 251614 625 252795 626 254006 627 255195 628 256414 629 257610 630 258837 631 260041 632 261275 633 262486 634 263728 635 264947 636 266197 637 267424 638 268681 639 269915 640 271180 641 272422 642 273695 643 274945 644 276226 645 277483 646 278771 647 280036 648 281333 649 282606 650 283910 651 285191 652 286503 653 287791 654 289111 655 290408 656 291736 657 293040 658 294376 659 295688 660 297032 661 298352 662 299704 663 301032 664 302392 665 303728 666 305096 667 306440 668 307816 669 309168 670 310552 671 311912 672 313305 673 314673 674 316073 675 317449 676 318858 677 320242 678 321659 679 323052 680 324477 681 325877 682 327310 683 328719 684 330161 685 331578 686 333028 687 334453 688 335911 689 337344 690 338811 691 340253 692 341728 693 343178 694 344661 695 346119 696 347611 697 349078 698 350578 699 352053 700 353562 701 355045 702 356562 703 358054 704 359580 705 361080 706 362614 707 364123 708 365666 709 367183 710 368734 711 370260 712 371820 713 373354 714 374923 715 376466 716 378043 717 379594 718 381180 719 382740 720 384335 721 385904 722 387507 723 389084 724 390696 725 392282 726 393903 727 395498 728 397128 729 398731 730 400369 731 401981 732 403629 733 405250 734 406906 735 408536 736 410201 737 411839 738 413513 739 415161 740 416844 741 418500 742 420192 743 421857 744 423558 745 425232 746 426942 747 428625 748 430344 749 432036 750 433764 751 435465 752 437202 753 438912 754 440658 755 442377 756 444133 757 445861 758 447625 759 449362 760 451136 761 452882 762 454665 763 456421 764 458213 765 459977 766 461778 767 463552 768 465363 769 467146 770 468966 771 470758 772 472587 773 474388 774 476227 775 478038 776 479886 777 481706 778 483563 779 485392 780 487259 781 489098 782 490974 783 492822 784 494708 785 496565 786 498460 787 500327 788 502232 789 504108 790 506022 791 507908 792 509832 793 511727 794 513660 795 515565 796 517508 797 519422 798 521375 799 523299 800 525261 801 527194 802 529166 803 531109 804 533091 805 535044 806 537035 807 538997 808 540998 809 542970 810 544981 811 546963 812 548984 813 550975 814 553005 815 555006 816 557047 817 559058 818 561108 819 563129 820 565189 821 567219 822 569289 823 571330 824 573410 825 575460 826 577550 827 579610 828 581710 829 583780 830 585890 831 587970 832 590090 833 592180 834 594310 835 596410 836 598550 837 600660 838 602810 839 604930 840 607091 841 609221 842 611391 843 613531 844 615712 845 617862 846 620053 847 622214 848 624415 849 626585 850 628796 851 630977 852 633199 853 635390 854 637622 855 639823 856 642065 857 644276 858 646529 859 648751 860 651014 861 653246 862 655519 863 657761 864 660045 865 662298 866 664592 867 666855 868 669160 869 671433 870 673748 871 676032 872 678358 873 680652 874 682988 875 685293 876 687640 877 689955 878 692312 879 694638 880 697006 881 699342 882 701721 883 704068 884 706457 885 708814 886 711214 887 713582 888 715993 889 718372 890 720793 891 723182 892 725614 893 728014 894 730457 895 732868 896 735322 897 737743 898 740207 899 742639 900 745115 901 747558 902 750044 903 752498 904 754995 905 757459 906 759967 907 762443 908 764962 909 767448 910 769978 911 772475 912 775016 913 777524 914 780076 915 782595 916 785158 917 787688 918 790262 919 792803 920 795388 921 797940 922 800536 923 803099 924 805707 925 808281 926 810899 927 813484 928 816114 929 818710 930 821351 931 823959 932 826611 933 829229 934 831892 935 834522 936 837197 937 839838 938 842524 939 845176 940 847873 941 850536 942 853245 943 855920 944 858640 945 861326 946 864057 947 866754 948 869497 949 872206 950 874960 951 877680 952 880446 953 883177 954 885954 955 888697 956 891486 957 894240 958 897040 959 899806 960 902618 961 905395 962 908218 963 911007 964 913842 965 916642 966 919489 967 922301 968 925159 969 927982 970 930852 971 933687 972 936569 973 939416 974 942309 975 945167 976 948072 977 950942 978 953859 979 956741 980 959670 981 962563 982 965503 983 968408 984 971361 985 974278 986 977242 987 980171 988 983147 989 986087 990 989075 991 992028 992 995028 993 997992 994 1001004 995 1003980 996 1007004 997 1009992 998 1013028 999 1016028 1000 1019076