0 1 1 0 2 0 3 1 4 0 5 1 6 2 7 1 8 1 9 2 10 2 11 2 12 4 13 3 14 3 15 5 16 4 17 5 18 7 19 6 20 7 21 9 22 8 23 9 24 12 25 11 26 12 27 15 28 14 29 15 30 19 31 18 32 19 33 23 34 22 35 24 36 28 37 27 38 29 39 33 40 33 41 35 42 40 43 39 44 41 45 47 46 46 47 49 48 55 49 54 50 57 51 63 52 63 53 66 54 73 55 73 56 76 57 83 58 83 59 87 60 95 61 95 62 99 63 107 64 107 65 112 66 121 67 121 68 126 69 135 70 136 71 141 72 151 73 152 74 157 75 168 76 169 77 175 78 186 79 187 80 194 81 205 82 207 83 214 84 226 85 228 86 235 87 248 88 250 89 258 90 272 91 274 92 282 93 296 94 299 95 308 96 323 97 326 98 335 99 350 100 354 101 364 102 380 103 384 104 394 105 411 106 415 107 426 108 444 109 448 110 460 111 478 112 483 113 495 114 514 115 520 116 532 117 552 118 558 119 571 120 592 121 598 122 612 123 633 124 640 125 655 126 677 127 684 128 699 129 722 130 730 131 746 132 770 133 778 134 794 135 819 136 828 137 845 138 871 139 880 140 898 141 924 142 934 143 953 144 980 145 991 146 1010 147 1038 148 1049 149 1069 150 1099 151 1110 152 1131 153 1161 154 1173 155 1195 156 1226 157 1239 158 1261 159 1293 160 1307 161 1330 162 1363 163 1377 164 1401 165 1435 166 1450 167 1475 168 1510 169 1525 170 1551 171 1587 172 1603 173 1630 174 1667 175 1684 176 1711 177 1749 178 1767 179 1795 180 1835 181 1853 182 1882 183 1922 184 1941 185 1972 186 2013 187 2033 188 2064 189 2106 190 2127 191 2159 192 2203 193 2224 194 2257 195 2302 196 2324 197 2358 198 2404 199 2427 200 2462 201 2509 202 2533 203 2569 204 2617 205 2642 206 2679 207 2728 208 2754 209 2792 210 2843 211 2869 212 2908 213 2960 214 2987 215 3028 216 3081 217 3109 218 3150 219 3204 220 3234 221 3276 222 3332 223 3362 224 3405 225 3462 226 3493 227 3538 228 3596 229 3628 230 3674 231 3733 232 3766 233 3813 234 3874 235 3908 236 3956 237 4018 238 4053 239 4102 240 4166 241 4202 242 4252 243 4317 244 4354 245 4406 246 4472 247 4510 248 4563 249 4630 250 4670 251 4724 252 4793 253 4833 254 4888 255 4959 256 5000 257 5057 258 5129 259 5171 260 5229 261 5302 262 5346 263 5405 264 5480 265 5525 266 5585 267 5661 268 5707 269 5769 270 5847 271 5894 272 5957 273 6036 274 6084 275 6149 276 6230 277 6279 278 6345 279 6427 280 6478 281 6545 282 6629 283 6681 284 6749 285 6835 286 6888 287 6958 288 7045 289 7099 290 7171 291 7259 292 7315 293 7388 294 7478 295 7535 296 7609 297 7701 298 7759 299 7835 300 7929 301 7988 302 8065 303 8160 304 8221 305 8300 306 8397 307 8459 308 8539 309 8637 310 8701 311 8783 312 8883 313 8948 314 9031 315 9133 316 9199 317 9284 318 9388 319 9455 320 9542 321 9647 322 9716 323 9804 324 9911 325 9982 326 10071 327 10180 328 10252 329 10343 330 10454 331 10527 332 10620 333 10732 334 10807 335 10902 336 11016 337 11092 338 11188 339 11304 340 11382 341 11480 342 11598 343 11677 344 11776 345 11896 346 11977 347 12078 348 12200 349 12282 350 12385 351 12508 352 12592 353 12697 354 12822 355 12908 356 13014 357 13141 358 13228 359 13336 360 13466 361 13554 362 13664 363 13795 364 13885 365 13997 366 14130 367 14222 368 14335 369 14470 370 14564 371 14679 372 14816 373 14911 374 15028 375 15167 376 15264 377 15383 378 15524 379 15622 380 15743 381 15886 382 15986 383 16109 384 16254 385 16356 386 16480 387 16627 388 16731 389 16857 390 17007 391 17112 392 17240 393 17391 394 17498 395 17629 396 17782 397 17891 398 18023 399 18178 400 18289 401 18423 402 18581 403 18693 404 18829 405 18989 406 19103 407 19241 408 19403 409 19519 410 19659 411 19823 412 19941 413 20083 414 20249 415 20369 416 20513 417 20681 418 20803 419 20949 420 21120 421 21243 422 21391 423 21564 424 21689 425 21840 426 22015 427 22142 428 22294 429 22471 430 22601 431 22755 432 22935 433 23066 434 23222 435 23404 436 23537 437 23696 438 23880 439 24015 440 24176 441 24362 442 24499 443 24662 444 24851 445 24990 446 25155 447 25346 448 25487 449 25654 450 25848 451 25991 452 26160 453 26356 454 26501 455 26673 456 26871 457 27018 458 27192 459 27392 460 27542 461 27718 462 27921 463 28072 464 28250 465 28456 466 28609 467 28790 468 28998 469 29153 470 29336 471 29546 472 29704 473 29889 474 30102 475 30262 476 30449 477 30664 478 30826 479 31016 480 31234 481 31398 482 31590 483 31810 484 31976 485 32171 486 32394 487 32562 488 32759 489 32984 490 33155 491 33354 492 33582 493 33755 494 33956 495 34187 496 34362 497 34566 498 34799 499 34976 500 35183 501 35418 502 35598 503 35807 504 36045 505 36227 506 36438 507 36679 508 36863 509 37077 510 37321 511 37507 512 37723 513 37969 514 38158 515 38377 516 38626 517 38817 518 39038 519 39289 520 39483 521 39707 522 39961 523 40157 524 40383 525 40640 526 40838 527 41067 528 41327 529 41527 530 41759 531 42021 532 42224 533 42458 534 42723 535 42929 536 43165 537 43433 538 43641 539 43880 540 44151 541 44361 542 44603 543 44876 544 45089 545 45334 546 45610 547 45825 548 46072 549 46351 550 46569 551 46819 552 47101 553 47321 554 47573 555 47858 556 48081 557 48336 558 48624 559 48849 560 49107 561 49397 562 49625 563 49886 564 50179 565 50410 566 50673 567 50969 568 51202 569 51468 570 51768 571 52003 572 52272 573 52574 574 52812 575 53084 576 53389 577 53630 578 53904 579 54212 580 54456 581 54733 582 55044 583 55290 584 55570 585 55884 586 56133 587 56416 588 56733 589 56984 590 57270 591 57590 592 57844 593 58133 594 58456 595 58713 596 59004 597 59330 598 59590 599 59884 600 60214 601 60476 602 60773 603 61105 604 61370 605 61671 606 62006 607 62274 608 62577 609 62915 610 63186 611 63492 612 63834 613 64107 614 64416 615 64761 616 65037 617 65349 618 65697 619 65976 620 66291 621 66642 622 66924 623 67242 624 67596 625 67881 626 68202 627 68559 628 68847 629 69171 630 69532 631 69822 632 70149 633 70513 634 70806 635 71137 636 71504 637 71800 638 72133 639 72503 640 72803 641 73139 642 73513 643 73815 644 74154 645 74531 646 74836 647 75179 648 75559 649 75867 650 76213 651 76596 652 76907 653 77256 654 77643 655 77957 656 78309 657 78699 658 79016 659 79371 660 79765 661 80085 662 80443 663 80840 664 81163 665 81525 666 81925 667 82251 668 82616 669 83019 670 83349 671 83717 672 84124 673 84456 674 84827 675 85238 676 85573 677 85948 678 86362 679 86700 680 87078 681 87495 682 87837 683 88218 684 88639 685 88984 686 89368 687 89792 688 90140 689 90528 690 90956 691 91307 692 91698 693 92129 694 92483 695 92878 696 93313 697 93670 698 94068 699 94506 700 94867 701 95268 702 95710 703 96074 704 96478 705 96924 706 97291 707 97699 708 98148 709 98518 710 98930 711 99382 712 99756 713 100171 714 100627 715 101004 716 101422 717 101882 718 102262 719 102684 720 103148 721 103531 722 103956 723 104423 724 104810 725 105239 726 105710 727 106100 728 106532 729 107006 730 107400 731 107836 732 108314 733 108711 734 109150 735 109632 736 110032 737 110475 738 110961 739 111364 740 111811 741 112300 742 112707 743 113157 744 113650 745 114061 746 114514 747 115011 748 115425 749 115882 750 116383 751 116800 752 117261 753 117765 754 118186 755 118651 756 119159 757 119583 758 120051 759 120563 760 120991 761 121463 762 121979 763 122410 764 122885 765 123405 766 123840 767 124319 768 124843 769 125281 770 125764 771 126291 772 126733 773 127220 774 127751 775 128197 776 128687 777 129222 778 129671 779 130165 780 130705 781 131157 782 131655 783 132198 784 132654 785 133156 786 133703 787 134163 788 134668 789 135219 790 135683 791 136192 792 136747 793 137214 794 137727 795 138286 796 138757 797 139274 798 139837 799 140311 800 140832 801 141399 802 141877 803 142402 804 142973 805 143455 806 143983 807 144558 808 145044 809 145576 810 146156 811 146645 812 147181 813 147764 814 148257 815 148798 816 149385 817 149882 818 150426 819 151017 820 151518 821 152066 822 152662 823 153166 824 153718 825 154318 826 154826 827 155382 828 155986 829 156498 830 157058 831 157666 832 158182 833 158746 834 159358 835 159878 836 160446 837 161062 838 161586 839 162158 840 162779 841 163306 842 163882 843 164507 844 165038 845 165619 846 166248 847 166783 848 167367 849 168000 850 168540 851 169128 852 169766 853 170309 854 170901 855 171543 856 172090 857 172687 858 173333 859 173884 860 174485 861 175135 862 175690 863 176295 864 176950 865 177509 866 178118 867 178777 868 179340 869 179953 870 180617 871 181184 872 181801 873 182469 874 183040 875 183662 876 184334 877 184909 878 185535 879 186211 880 186791 881 187421 882 188102 883 188685 884 189319 885 190005 886 190592 887 191231 888 191921 889 192512 890 193155 891 193849 892 194445 893 195092 894 195791 895 196391 896 197042 897 197745 898 198349 899 199005 900 199713 901 200321 902 200981 903 201693 904 202305 905 202970 906 203687 907 204303 908 204972 909 205693 910 206314 911 206987 912 207713 913 208338 914 209015 915 209746 916 210375 917 211057 918 211792 919 212425 920 213112 921 213851 922 214489 923 215180 924 215924 925 216566 926 217261 927 218010 928 218656 929 219356 930 220110 931 220760 932 221464 933 222222 934 222877 935 223586 936 224349 937 225008 938 225721 939 226488 940 227152 941 227870 942 228642 943 229310 944 230032 945 230809 946 231481 947 232208 948 232990 949 233666 950 234398 951 235184 952 235865 953 236601 954 237392 955 238078 956 238818 957 239614 958 240304 959 241049 960 241850 961 242544 962 243294 963 244099 964 244798 965 245553 966 246363 967 247066 968 247825 969 248640 970 249348 971 250112 972 250932 973 251644 974 252412 975 253237 976 253954 977 254727 978 255557 979 256278 980 257056 981 257890 982 258616 983 259399 984 260238 985 260969 986 261756 987 262600 988 263335 989 264127 990 264977 991 265716 992 266513 993 267367 994 268111 995 268913 996 269772 997 270521 998 271327 999 272191 1000 272945