2 1 3 2 4 4 5 9 6 13 7 22 8 27 9 39 10 47 11 61 12 71 13 91 14 100 15 122 16 137 17 160 18 175 19 205 20 220 21 253 22 272 23 304 24 326 25 368 26 386 27 427 28 455 29 497 30 523 31 575 32 598 33 651 34 683 35 733 36 768 37 830 38 856 39 918 40 959 41 1021 42 1056 43 1129 44 1162 45 1236 46 1281 47 1347 48 1393 49 1479 50 1514 51 1596 52 1648 53 1727 54 1775 55 1869 56 1914 57 2007 58 2061 59 2147 60 2205 61 2315 62 2355 63 2457 64 2525 65 2622 66 2682 67 2794 68 2847 69 2962 70 3030 71 3137 72 3203 73 3333 74 3383 75 3505 76 3587 77 3700 78 3771 79 3906 80 3969 81 4108 82 4183 83 4304 84 4386 85 4539 86 4600 87 4738 88 4831 89 4967 90 5047 91 5209 92 5276 93 5430 94 5522 95 5662 96 5759 97 5929 98 5997 99 6160 100 6265 101 6421 102 6507 103 6686 104 6768 105 6946 106 7053 107 7204 108 7310 109 7506 110 7583 111 7769 112 7881 113 8056 114 8155 115 8355 116 8450 117 8642 118 8759 119 8934 120 9054 121 9275 122 9352 123 9553 124 9685 125 9876 126 9994 127 10213 128 10310 129 10529 130 10655 131 10854 132 10977 133 11217 134 11312 135 11531 136 11681 137 11884 138 12007 139 12250 140 12361 141 12607 142 12736 143 12948 144 13091 145 13354 146 13457 147 13692 148 13852 149 14077 150 14213 151 14483 152 14595 153 14856 154 15007 155 15238 156 15393 157 15669 158 15779 159 16041 160 16212 161 16467 162 16605 163 16888 164 17016 165 17296 166 17466 167 17705 168 17871 169 18182 170 18295 171 18582 172 18758 173 19021 174 19179 175 19486 176 19634 177 19925 178 20097 179 20363 180 20541 181 20878 182 20993 183 21299 184 21490 185 21776 186 21948 187 22267 188 22417 189 22737 190 22930 191 23215 192 23394 193 23745 194 23879 195 24201 196 24418 197 24713 198 24888 199 25240 200 25396 201 25747 202 25932 203 26234 204 26439 205 26806 206 26958 207 27290 208 27515 209 27837 210 28025 211 28407 212 28556 213 28918 214 29130 215 29450 216 29671 217 30059 218 30210 219 30567 220 30803 221 31153 222 31341 223 31732 224 31910 225 32301 226 32524 227 32847 228 33073 229 33488 230 33651 231 34042 232 34283 233 34637 234 34846 235 35262 236 35453 237 35845 238 36081 239 36442 240 36674 241 37125 242 37276 243 37679 244 37941 245 38315 246 38551 247 38968 248 39166 249 39592 250 39836 251 40220 252 40456 253 40922 254 41093 255 41513 256 41797 257 42182 258 42412 259 42868 260 43079 261 43529 262 43775 263 44164 264 44426 265 44912 266 45102 267 45536 268 45817 269 46231 270 46477 271 46969 272 47165 273 47634 274 47905 275 48308 276 48593 277 49080 278 49276 279 49738 280 50042 281 50492 282 50720 283 51218 284 51444 285 51930 286 52224 287 52640 288 52928 289 53454 290 53649 291 54141 292 54438 293 54889 294 55157 295 55683 296 55920 297 56416 298 56712 299 57152 300 57451 301 58010 302 58209 303 58704 304 59031 305 59506 306 59789 307 60319 308 60558 309 61093 310 61391 311 61867 312 62159 313 62733 314 62948 315 63470 316 63829 317 64290 318 64580 319 65142 320 65399 321 65962 322 66257 323 66745 324 67060 325 67653 326 67890 327 68414 328 68767 329 69278 330 69579 331 70172 332 70413 333 70981 334 71316 335 71812 336 72157 337 72766 338 72989 339 73552 340 73916 341 74457 342 74750 343 75356 344 75630 345 76215 346 76565 347 77065 348 77411 349 78046 350 78294 351 78897 352 79251 353 79796 354 80109 355 80735 356 81030 357 81622 358 81985 359 82512 360 82870 361 83553 362 83774 363 84375 364 84769 365 85338 366 85672 367 86301 368 86594 369 87230 370 87595 371 88159 372 88513 373 89183 374 89448 375 90073 376 90487 377 91054 378 91395 379 92074 380 92360 381 93027 382 93382 383 93954 384 94336 385 95043 386 95330 387 95941 388 96363 389 96958 390 97314 391 98023 392 98310 393 98993 394 99367 395 99957 396 100364 397 101075 398 101347 399 102009 400 102448 401 103079 402 103413 403 104124 404 104448 405 105138 406 105560 407 106150 408 106548 409 107295 410 107577 411 108275 412 108695 413 109332 414 109717 415 110445 416 110784 417 111484 418 111890 419 112520 420 112934 421 113729 422 113986 423 114688 424 115149 425 115805 426 116202 427 116934 428 117282 429 118005 430 118438 431 119094 432 119499 433 120299 434 120591 435 121322 436 121795 437 122446 438 122847 439 123621 440 123972 441 124754 442 125167 443 125815 444 126254 445 127064 446 127394 447 128114 448 128597 449 129307 450 129697 451 130519 452 130846 453 131616 454 132068 455 132748 456 133227 457 134031 458 134346 459 135108 460 135610 461 136335 462 136728 463 137560 464 137911 465 138713 466 139184 467 139857 468 140323 469 141186 470 141517 471 142307 472 142788 473 143524 474 143952 475 144787 476 145183 477 145985 478 146452 479 147162 480 147640 481 148547 482 148848 483 149647 484 150178 485 150918 486 151373 487 152215 488 152597 489 153439 490 153919 491 154683 492 155131 493 156029 494 156380 495 157204 496 157761 497 158499 498 158952 499 159822 500 160221 501 161099 502 161568 503 162320 504 162822 505 163768 506 164111 507 164932 508 165476 509 166259 510 166725 511 167652 512 168036 513 168909 514 169416 515 170178 516 170709 517 171626 518 171996 519 172865 520 173412 521 174248 522 174681 523 175611 524 176021 525 176919 526 177472 527 178219 528 178746 529 179722 530 180081 531 180983 532 181531 533 182359 534 182834 535 183776 536 184221 537 185120 538 185647 539 186453 540 187004 541 188006 542 188345 543 189247 544 189834 545 190686 546 191190 547 192145 548 192562 549 193501 550 194055 551 194900 552 195412 553 196427 554 196817 555 197726 556 198346 557 199177 558 199687 559 200682 560 201124 561 202126 562 202628 563 203463 564 204025 565 205055 566 205474 567 206388 568 207018 569 207883 570 208394 571 209430 572 209849 573 210837 574 211400 575 212272 576 212850 577 213889 578 214276 579 215239 580 215863 581 216786 582 217292 583 218309 584 218779 585 219783 586 220387 587 221223 588 221809 589 222896 590 223297 591 224302 592 224906 593 225832 594 226363 595 227427 596 227918 597 228894 598 229490 599 230390 600 230984 601 232117 602 232492 603 233506 604 234147 605 235074 606 235652 607 236690 608 237175 609 238228 610 238834 611 239758 612 240335 613 241458 614 241881 615 242903 616 243590 617 244537 618 245068 619 246162 620 246657 621 247746 622 248335 623 249258 624 249891 625 251031 626 251477 627 252487 628 253170 629 254136 630 254714 631 255879 632 256313 633 257404 634 258025 635 258975 636 259630 637 260761 638 261227 639 262275 640 262967 641 263987 642 264521 643 265658 644 266172 645 267291 646 267939 647 268875 648 269518 649 270720 650 271162 651 272269 652 272940 653 273933 654 274531 655 275689 656 276234 657 277337 658 277987 659 278978 660 279618 661 280861 662 281278 663 282380 664 283102 665 284133 666 284765 667 285903 668 286426 669 287570 670 288238 671 289270 672 289905 673 291155 674 291597 675 292719 676 293481 677 294484 678 295099 679 296300 680 296855 681 298045 682 298669 683 299697 684 300372 685 301632 686 302127 687 303250 688 303974 689 305050 690 305670 691 306920 692 307427 693 308613 694 309330 695 310338 696 311055 697 312302 698 312785 699 313945 700 314701 701 315831 702 316410 703 317666 704 318212 705 319434 706 320142 707 321162 708 321880 709 323157 710 323660 711 324871 712 325605 713 326707 714 327349 715 328631 716 329211 717 330393 718 331109 719 332185 720 332903 721 334276 722 334723 723 335909 724 336689 725 337810 726 338499 727 339754 728 340328 729 341607 730 342304 731 343417 732 344105 733 345440 734 345960 735 347182 736 348018 737 349113 738 349776 739 351087 740 351666 741 352966 742 353665 743 354787 744 355508 745 356878 746 357417 747 358622 748 359438 749 360594 750 361284 751 362630 752 363181 753 364482 754 365218 755 366353 756 367127 757 368499 758 368999 759 370261 760 371088 761 372302 762 372936 763 374286 764 374909 765 376201 766 377003 767 378098 768 378868 769 380280 770 380809 771 382145 772 382903 773 384098 774 384806 775 386187 776 386821 777 388122 778 388899 779 390046 780 390826 781 392292 782 392793 783 394091 784 394944 785 396176 786 396881 787 398234 788 398863 789 400214 790 401002 791 402219 792 402976 793 404434 794 404964 795 406281 796 407170 797 408360 798 409090 799 410524 800 411139 801 412557 802 413297 803 414488 804 415296 805 416759 806 417371 807 418658 808 419525 809 420787 810 421514 811 422998 812 423580 813 424990 814 425777 815 427004 816 427837 817 429305 818 429865 819 431225 820 432139 821 433408 822 434108 823 435564 824 436222 825 437646 826 438493 827 439696 828 440499 829 442024 830 442598 831 444014 832 444863 833 446170 834 446926 835 448381 836 449076 837 450477 838 451313 839 452557 840 453395 841 455004 842 455500 843 456901 844 457813 845 459120 846 459926 847 461389 848 462074 849 463515 850 464345 851 465657 852 466453 853 468009 854 468614 855 470055 856 470998 857 472275 858 473045 859 474577 860 475250 861 476762 862 477584 863 478854 864 479716 865 481323 866 481931 867 483330 868 484270 869 485631 870 486408 871 487982 872 488624 873 490126 874 490992 875 492293 876 493209 877 494745 878 495367 879 496829 880 497780 881 499204 882 499929 883 501523 884 502188 885 503711 886 504618 887 505898 888 506784 889 508420 890 509050 891 510548 892 511475 893 512835 894 513655 895 515237 896 515982 897 517510 898 518366 899 519706 900 520605 901 522305 902 522869 903 524375 904 525360 905 526749 906 527592 907 529152 908 529877 909 531434 910 532352 911 533768 912 534591 913 536275 914 536907 915 538421 916 539444 917 540813 918 541669 919 543290 920 544006 921 545637 922 546482 923 547864 924 548791 925 550506 926 551153 927 552648 928 553661 929 555102 930 555933 931 557624 932 558324 933 559898 934 560830 935 562230 936 563205 937 564891 938 565515 939 567097 940 568086 941 569583 942 570386 943 572055 944 572810 945 574444 946 575432 947 576769 948 577705 949 579438 950 580116 951 581734 952 582703 953 584215 954 585040 955 586742 956 587521 957 589113 958 590077 959 591504 960 592479 961 594276 962 594870 963 596477 964 597522 965 599002 966 599918 967 601606 968 602348 969 604029 970 604975 971 606464 972 607376 973 609166 974 609856 975 611455 976 612552 977 614020 978 614894 979 616627 980 617417 981 619154 982 620054 983 621513 984 622495 985 624308 986 625021 987 626618 988 627701 989 629214 990 630112 991 631933 992 632633 993 634351 994 635320 995 636831 996 637830 997 639601 998 640308 999 641970 1000 643063