0 1 1 0 2 0 3 1 4 1 5 1 6 2 7 1 8 2 9 3 10 3 11 3 12 5 13 4 14 5 15 7 16 7 17 7 18 10 19 9 20 11 21 13 22 13 23 14 24 18 25 17 26 19 27 22 28 23 29 24 30 29 31 28 32 31 33 35 34 36 35 38 36 44 37 43 38 47 39 52 40 54 41 56 42 63 43 63 44 68 45 74 46 76 47 79 48 88 49 88 50 94 51 101 52 104 53 108 54 118 55 119 56 126 57 134 58 138 59 143 60 155 61 156 62 164 63 174 64 179 65 185 66 198 67 200 68 210 69 221 70 227 71 234 72 249 73 252 74 263 75 276 76 283 77 291 78 308 79 312 80 325 81 339 82 347 83 357 84 376 85 381 86 395 87 411 88 421 89 432 90 453 91 459 92 475 93 493 94 504 95 517 96 540 97 547 98 565 99 585 100 598 101 612 102 637 103 646 104 666 105 688 106 702 107 718 108 746 109 756 110 778 111 802 112 818 113 836 114 866 115 878 116 902 117 928 118 946 119 966 120 999 121 1012 122 1038 123 1067 124 1087 125 1109 126 1144 127 1159 128 1188 129 1219 130 1241 131 1265 132 1303 133 1320 134 1351 135 1385 136 1409 137 1435 138 1476 139 1495 140 1529 141 1565 142 1591 143 1620 144 1664 145 1685 146 1721 147 1760 148 1789 149 1820 150 1867 151 1890 152 1929 153 1971 154 2002 155 2036 156 2086 157 2111 158 2153 159 2198 160 2232 161 2268 162 2321 163 2349 164 2394 165 2442 166 2478 167 2517 168 2574 169 2604 170 2652 171 2703 172 2742 173 2784 174 2844 175 2877 176 2928 177 2982 178 3024 179 3069 180 3133 181 3168 182 3222 183 3280 184 3325 185 3373 186 3440 187 3478 188 3536 189 3597 190 3645 191 3696 192 3767 193 3808 194 3869 195 3934 196 3985 197 4039 198 4114 199 4158 200 4223 201 4291 202 4345 203 4403 204 4482 205 4529 206 4597 207 4669 208 4727 209 4788 210 4871 211 4921 212 4993 213 5069 214 5130 215 5195 216 5282 217 5335 218 5411 219 5491 220 5556 221 5624 222 5715 223 5772 224 5852 225 5936 226 6004 227 6076 228 6172 229 6232 230 6316 231 6404 232 6476 233 6552 234 6652 235 6716 236 6804 237 6896 238 6972 239 7052 240 7157 241 7224 242 7316 243 7413 244 7493 245 7577 246 7686 247 7757 248 7854 249 7955 250 8039 251 8127 252 8241 253 8316 254 8417 255 8523 256 8611 257 8703 258 8822 259 8901 260 9007 261 9117 262 9209 263 9306 264 9430 265 9513 266 9623 267 9738 268 9835 269 9936 270 10065 271 10152 272 10267 273 10387 274 10488 275 10594 276 10728 277 10819 278 10939 279 11064 280 11170 281 11280 282 11419 283 11515 284 11640 285 11770 286 11880 287 11995 288 12140 289 12240 290 12370 291 12505 292 12620 293 12740 294 12890 295 12995 296 13130 297 13270 298 13390 299 13515 300 13671 301 13780 302 13920 303 14066 304 14191 305 14321 306 14482 307 14596 308 14742 309 14893 310 15023 311 15158 312 15325 313 15444 314 15595 315 15752 316 15887 317 16027 318 16200 319 16324 320 16481 321 16643 322 16783 323 16929 324 17108 325 17237 326 17399 327 17567 328 17713 329 17864 330 18049 331 18183 332 18351 333 18525 334 18676 335 18833 336 19024 337 19163 338 19337 339 19517 340 19674 341 19836 342 20033 343 20178 344 20358 345 20544 346 20706 347 20874 348 21078 349 21228 350 21414 351 21606 352 21774 353 21948 354 22158 355 22314 356 22506 357 22704 358 22878 359 23058 360 23275 361 23436 362 23634 363 23839 364 24019 365 24205 366 24428 367 24595 368 24800 369 25011 370 25197 371 25389 372 25619 373 25792 374 26003 375 26221 376 26413 377 26611 378 26848 379 27027 380 27245 381 27469 382 27667 383 27872 384 28116 385 28301 386 28525 387 28756 388 28961 389 29172 390 29423 391 29614 392 29845 393 30083 394 30294 395 30512 396 30770 397 30967 398 31205 399 31450 400 31668 401 31892 402 32157 403 32361 404 32606 405 32858 406 33082 407 33313 408 33586 409 33796 410 34048 411 34307 412 34538 413 34776 414 35056 415 35273 416 35532 417 35798 418 36036 419 36281 420 36569 421 36792 422 37058 423 37332 424 37577 425 37829 426 38124 427 38354 428 38628 429 38909 430 39161 431 39420 432 39723 433 39960 434 40241 435 40530 436 40789 437 41055 438 41366 439 41610 440 41899 441 42195 442 42461 443 42735 444 43054 445 43305 446 43601 447 43905 448 44179 449 44460 450 44787 451 45045 452 45349 453 45661 454 45942 455 46231 456 46566 457 46831 458 47143 459 47463 460 47752 461 48048 462 48391 463 48664 464 48984 465 49312 466 49608 467 49912 468 50264 469 50544 470 50872 471 51208 472 51512 473 51824 474 52184 475 52472 476 52808 477 53152 478 53464 479 53784 480 54153 481 54448 482 54792 483 55145 484 55465 485 55793 486 56170 487 56473 488 56826 489 57187 490 57515 491 57851 492 58237 493 58548 494 58909 495 59279 496 59615 497 59959 498 60354 499 60673 500 61043 501 61421 502 61765 503 62118 504 62522 505 62849 506 63227 507 63614 508 63967 509 64328 510 64741 511 65076 512 65463 513 65859 514 66220 515 66590 516 67012 517 67355 518 67751 519 68156 520 68526 521 68904 522 69335 523 69687 524 70092 525 70506 526 70884 527 71271 528 71712 529 72072 530 72486 531 72909 532 73296 533 73692 534 74142 535 74511 536 74934 537 75366 538 75762 539 76167 540 76627 541 77004 542 77436 543 77878 544 78283 545 78697 546 79166 547 79552 548 79994 549 80445 550 80859 551 81282 552 81761 553 82156 554 82607 555 83068 556 83491 557 83923 558 84412 559 84816 560 85277 561 85747 562 86179 563 86621 564 87120 565 87533 566 88003 567 88483 568 88925 569 89376 570 89885 571 90307 572 90787 573 91277 574 91728 575 92189 576 92708 577 93139 578 93629 579 94129 580 94590 581 95060 582 95589 583 96030 584 96530 585 97040 586 97510 587 97990 588 98530 589 98980 590 99490 591 100010 592 100490 593 100980 594 101530 595 101990 596 102510 597 103040 598 103530 599 104030 600 104591 601 105060 602 105590 603 106131 604 106631 605 107141 606 107712 607 108191 608 108732 609 109283 610 109793 611 110313 612 110895 613 111384 614 111935 615 112497 616 113017 617 113547 618 114140 619 114639 620 115201 621 115773 622 116303 623 116844 624 117448 625 117957 626 118529 627 119112 628 119653 629 120204 630 120819 631 121338 632 121921 633 122515 634 123066 635 123628 636 124254 637 124783 638 125377 639 125982 640 126544 641 127116 642 127753 643 128293 644 128898 645 129514 646 130086 647 130669 648 131318 649 131868 650 132484 651 133111 652 133694 653 134288 654 134948 655 135509 656 136136 657 136774 658 137368 659 137973 660 138645 661 139216 662 139854 663 140504 664 141109 665 141725 666 142408 667 142990 668 143640 669 144301 670 144917 671 145544 672 146239 673 146832 674 147493 675 148166 676 148793 677 149431 678 150138 679 150742 680 151415 681 152099 682 152737 683 153387 684 154106 685 154721 686 155405 687 156101 688 156751 689 157412 690 158143 691 158769 692 159465 693 160173 694 160834 695 161507 696 162250 697 162887 698 163595 699 164315 700 164988 701 165672 702 166427 703 167076 704 167796 705 168528 706 169212 707 169908 708 170676 709 171336 710 172068 711 172812 712 173508 713 174216 714 174996 715 175668 716 176412 717 177168 718 177876 719 178596 720 179389 721 180072 722 180828 723 181597 724 182317 725 183049 726 183854 727 184549 728 185318 729 186099 730 186831 731 187575 732 188393 733 189100 734 189881 735 190675 736 191419 737 192175 738 193006 739 193725 740 194519 741 195325 742 196081 743 196850 744 197694 745 198425 746 199231 747 200050 748 200819 749 201600 750 202457 751 203200 752 204019 753 204851 754 205632 755 206426 756 207296 757 208051 758 208883 759 209728 760 210522 761 211328 762 212211 763 212979 764 213824 765 214682 766 215488 767 216307 768 217204 769 217984 770 218842 771 219713 772 220532 773 221364 774 222274 775 223067 776 223938 777 224822 778 225654 779 226499 780 227423 781 228228 782 229112 783 230010 784 230855 785 231713 786 232650 787 233468 788 234366 789 235277 790 236135 791 237006 792 237957 793 238788 794 239699 795 240624 796 241495 797 242379 798 243344 799 244188 800 245113 801 246051 802 246935 803 247833 804 248812 805 249669 806 250607 807 251559 808 252457 809 253368 810 254361 811 255231 812 256183 813 257149 814 258060 815 258985 816 259992 817 260875 818 261841 819 262821 820 263746 821 264684 822 265705 823 266602 824 267582 825 268576 826 269514 827 270466 828 271502 829 272412 830 273406 831 274414 832 275366 833 276332 834 277382 835 278306 836 279314 837 280336 838 281302 839 282282 840 283347 841 284284 842 285306 843 286343 844 287323 845 288317 846 289396 847 290347 848 291384 849 292435 850 293429 851 294437 852 295531 853 296496 854 297547 855 298613 856 299621 857 300643 858 301752 859 302731 860 303797 861 304877 862 305899 863 306936 864 308060 865 309053 866 310133 867 311228 868 312265 869 313316 870 314455 871 315462 872 316557 873 317667 874 318718 875 319784 876 320938 877 321959 878 323069 879 324194 880 325260 881 326340 882 327509 883 328545 884 329670 885 330810 886 331890 887 332985 888 334170 889 335220 890 336360 891 337515 892 338610 893 339720 894 340920 895 341985 896 343140 897 344310 898 345420 899 346545 900 347761 901 348840 902 350010 903 351196 904 352321 905 353461 906 354692 907 355786 908 356972 909 358173 910 359313 911 360468 912 361715 913 362824 914 364025 915 365242 916 366397 917 367567 918 368830 919 369954 920 371171 921 372403 922 373573 923 374759 924 376038 925 377177 926 378409 927 379657 928 380843 929 382044 930 383339 931 384493 932 385741 933 387005 934 388206 935 389423 936 390734 937 391903 938 393167 939 394447 940 395664 941 396896 942 398223 943 399408 944 400688 945 401984 946 403216 947 404464 948 405808 949 407008 950 408304 951 409616 952 410864 953 412128 954 413488 955 414704 956 416016 957 417344 958 418608 959 419888 960 421265 961 422496 962 423824 963 425169 964 426449 965 427745 966 429138 967 430385 968 431730 969 433091 970 434387 971 435699 972 437109 973 438372 974 439733 975 441111 976 442423 977 443751 978 445178 979 446457 980 447835 981 449229 982 450557 983 451902 984 453346 985 454641 986 456035 987 457446 988 458791 989 460152 990 461613 991 462924 992 464335 993 465763 994 467124 995 468502 996 469980 997 471307 998 472735 999 474180 1000 475558