1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 2 27 1 28 2 29 1 30 2 31 1 32 2 33 1 34 2 35 1 36 2 37 1 38 2 39 3 40 3 41 3 42 5 43 4 44 5 45 6 46 6 47 6 48 8 49 7 50 8 51 9 52 10 53 10 54 12 55 12 56 13 57 14 58 15 59 15 60 17 61 17 62 18 63 19 64 20 65 21 66 22 67 23 68 24 69 25 70 26 71 27 72 28 73 29 74 30 75 31 76 32 77 33 78 35 79 36 80 38 81 40 82 42 83 44 84 47 85 49 86 52 87 55 88 58 89 61 90 65 91 69 92 72 93 76 94 80 95 84 96 89 97 93 98 99 99 103 100 108 101 113 102 119 103 124 104 131 105 138 106 143 107 149 108 156 109 162 110 169 111 177 112 185 113 191 114 199 115 206 116 214 117 223 118 231 119 241 120 248 121 257 122 265 123 275 124 284 125 294 126 305 127 313 128 323 129 333 130 345 131 355 132 367 133 380 134 389 135 401 136 413 137 426 138 438 139 452 140 466 141 477 142 491 143 505 144 520 145 534 146 550 147 566 148 579 149 595 150 611 151 628 152 644 153 662 154 680 155 695 156 714 157 731 158 751 159 769 160 789 161 809 162 827 163 847 164 867 165 889 166 909 167 931 168 954 169 974 170 997 171 1020 172 1045 173 1068 174 1094 175 1120 176 1144 177 1171 178 1198 179 1227 180 1255 181 1285 182 1316 183 1345 184 1377 185 1409 186 1444 187 1477 188 1513 189 1550 190 1585 191 1623 192 1662 193 1703 194 1743 195 1786 196 1830 197 1872 198 1918 199 1964 200 2013 201 2061 202 2112 203 2164 204 2215 205 2269 206 2324 207 2382 208 2439 209 2499 210 2561 211 2621 212 2685 213 2750 214 2818 215 2885 216 2956 217 3028 218 3099 219 3174 220 3250 221 3329 222 3408 223 3490 224 3574 225 3657 226 3744 227 3832 228 3924 229 4015 230 4110 231 4207 232 4303 233 4403 234 4505 235 4610 236 4715 237 4824 238 4935 239 5045 240 5160 241 5276 242 5396 243 5516 244 5640 245 5766 246 5892 247 6022 248 6154 249 6290 250 6426 251 6566 252 6709 253 6851 254 6998 255 7147 256 7300 257 7453 258 7611 259 7771 260 7931 261 8096 262 8263 263 8434 264 8606 265 8782 266 8961 267 9140 268 9324 269 9510 270 9701 271 9892 272 10088 273 10287 274 10486 275 10690 276 10897 277 11108 278 11320 279 11537 280 11757 281 11977 282 12203 283 12431 284 12664 285 12898 286 13137 287 13379 288 13622 289 13870 290 14121 291 14377 292 14634 293 14896 294 15162 295 15428 296 15700 297 15975 298 16255 299 16537 300 16823 301 17113 302 17404 303 17701 304 18001 305 18306 306 18613 307 18925 308 19241 309 19558 310 19881 311 20207 312 20540 313 20873 314 21212 315 21555 316 21899 317 22249 318 22603 319 22962 320 23323 321 23690 322 24062 323 24433 324 24812 325 25195 326 25582 327 25973 328 26368 329 26769 330 27170 331 27579 332 27990 333 28409 334 28828 335 29256 336 29686 337 30119 338 30559 339 31002 340 31451 341 31904 342 32361 343 32824 344 33289 345 33761 346 34235 347 34718 348 35202 349 35692 350 36189 351 36686 352 37191 353 37700 354 38216 355 38733 356 39259 357 39788 358 40321 359 40860 360 41404 361 41955 362 42508 363 43068 364 43635 365 44201 366 44777 367 45357 368 45944 369 46532 370 47130 371 47731 372 48335 373 48948 374 49564 375 50188 376 50815 377 51450 378 52089 379 52733 380 53383 381 54040 382 54703 383 55370 384 56045 385 56725 386 57408 387 58101 388 58796 389 59501 390 60210 391 60925 392 61645 393 62371 394 63103 395 63841 396 64588 397 65338 398 66095 399 66859 400 67627 401 68402 402 69185 403 69975 404 70771 405 71572 406 72381 407 73194 408 74015 409 74842 410 75680 411 76519 412 77367 413 78223 414 79081 415 79947 416 80823 417 81704 418 82592 419 83486 420 84389 421 85293 422 86209 423 87131 424 88061 425 88998 426 89941 427 90894 428 91848 429 92815 430 93787 431 94768 432 95756 433 96751 434 97753 435 98760 436 99779 437 100801 438 101834 439 102875 440 103919 441 104976 442 106035 443 107106 444 108181 445 109269 446 110362 447 111461 448 112573 449 113686 450 114814 451 115944 452 117089 453 118238 454 119394 455 120563 456 121734 457 122917 458 124106 459 125309 460 126514 461 127728 462 128956 463 130182 464 131426 465 132673 466 133934 467 135198 468 136474 469 137760 470 139048 471 140354 472 141662 473 142987 474 144314 475 145654 476 147004 477 148357 478 149728 479 151102 480 152491 481 153885 482 155292 483 156707 484 158127 485 159566 486 161005 487 162464 488 163926 489 165401 490 166885 491 168377 492 169885 493 171396 494 172928 495 174462 496 176012 497 177570 498 179138 499 180721 500 182309 501 183918 502 185530 503 187156 504 188794 505 190441 506 192102 507 193770 508 195460 509 197150 510 198860 511 200579 512 202308 513 204052 514 205806 515 207579 516 209356 517 211153 518 212959 519 214778 520 216611 521 218456 522 220320 523 222189 524 224079 525 225979 526 227890 527 229819 528 231760 529 233718 530 235684 531 237672 532 239667 533 241679 534 243707 535 245747 536 247806 537 249876 538 251965 539 254065 540 256183 541 258316 542 260465 543 262632 544 264812 545 267011 546 269223 547 271453 548 273700 549 275961 550 278244 551 280540 552 282854 553 285183 554 287532 555 289895 556 292278 557 294681 558 297098 559 299534 560 301989 561 304461 562 306951 563 309462 564 311993 565 314541 566 317108 567 319696 568 322301 569 324926 570 327573 571 330241 572 332925 573 335632 574 338360 575 341104 576 343871 577 346661 578 349470 579 352301 580 355153 581 358027 582 360919 583 363837 584 366776 585 369738 586 372723 587 375729 588 378761 589 381810 590 384888 591 387987 592 391111 593 394259 594 397430 595 400625 596 403842 597 407088 598 410354 599 413648 600 416968 601 420308 602 423679 603 427070 604 430491 605 433934 606 437409 607 440907 608 444430 609 447985 610 451560 611 455169 612 458800 613 462465 614 466154 615 469870 616 473619 617 477390 618 481194 619 485024 620 488889 621 492777 622 496695 623 500648 624 504621 625 508633 626 512670 627 516743 628 520841 629 524973 630 529138 631 533327 632 537557 633 541812 634 546107 635 550427 636 554784 637 559174 638 563591 639 568050 640 572536 641 577061 642 581616 643 586208 644 590833 645 595488 646 600187 647 604911 648 609681 649 614479 650 619316 651 624188 652 629094 653 634042 654 639020 655 644045 656 649099 657 654196 658 659328 659 664497 660 669709 661 674953 662 680246 663 685570 664 690936 665 696342 666 701786 667 707272 668 712794 669 718367 670 723969 671 729620 672 735310 673 741039 674 746813 675 752627 676 758490 677 764387 678 770335 679 776322 680 782353 681 788429 682 794548 683 800717 684 806923 685 813181 686 819481 687 825824 688 832217 689 838654 690 845141 691 851668 692 858250 693 864872 694 871544 695 878265 696 885032 697 891851 698 898715 699 905632 700 912594 701 919608 702 926672 703 933786 704 940953 705 948168 706 955437 707 962754 708 970125 709 977548 710 985021 711 992552 712 1000132 713 1007766 714 1015452 715 1023194 716 1030987 717 1038837 718 1046744 719 1054702 720 1062717 721 1070788 722 1078914 723 1087096 724 1095337 725 1103636 726 1111991 727 1120403 728 1128875 729 1137403 730 1145990 731 1154638 732 1163347 733 1172111 734 1180938 735 1189826 736 1198770 737 1207777 738 1216848 739 1225978 740 1235171 741 1244426 742 1253744 743 1263121 744 1272566 745 1282073 746 1291645 747 1301282 748 1310982 749 1320750 750 1330578 751 1340477 752 1350440 753 1360471 754 1370569 755 1380733 756 1390965 757 1401262 758 1411632 759 1422066 760 1432572 761 1443148 762 1453789 763 1464505 764 1475286 765 1486142 766 1497065 767 1508066 768 1519134 769 1530273 770 1541490 771 1552773 772 1564136 773 1575567 774 1587079 775 1598661 776 1610317 777 1622053 778 1633858 779 1645743 780 1657703 781 1669744 782 1681856 783 1694046 784 1706319 785 1718660 786 1731089 787 1743591 788 1756178 789 1768839 790 1781583 791 1794409 792 1807309 793 1820300 794 1833364 795 1846520 796 1859749 797 1873067 798 1886467 799 1899946 800 1913516 801 1927166 802 1940904 803 1954725 804 1968633 805 1982627 806 1996703 807 2010874 808 2025122 809 2039470 810 2053896 811 2068415 812 2083022 813 2097715 814 2112503 815 2127376 816 2142347 817 2157402 818 2172554 819 2187795 820 2203126 821 2218556 822 2234071 823 2249690 824 2265395 825 2281197 826 2297094 827 2313084 828 2329171 829 2345350 830 2361636 831 2378007 832 2394483 833 2411054 834 2427721 835 2444489 836 2461354 837 2478325 838 2495387 839 2512558 840 2529825 841 2547193 842 2564664 843 2582236 844 2599916 845 2617692 846 2635578 847 2653565 848 2671654 849 2689852 850 2708153 851 2726564 852 2745075 853 2763699 854 2782425 855 2801259 856 2820204 857 2839254 858 2858419 859 2877686 860 2897070 861 2916558 862 2936161 863 2955874 864 2975700 865 2995642 866 3015691 867 3035857 868 3056135 869 3076527 870 3097035 871 3117657 872 3138399 873 3159251 874 3180223 875 3201308 876 3222514 877 3243835 878 3265278 879 3286841 880 3308519 881 3330318 882 3352238 883 3374278 884 3396440 885 3418725 886 3441135 887 3463662 888 3486315 889 3509092 890 3531993 891 3555018 892 3578171 893 3601452 894 3624852 895 3648383 896 3672042 897 3695826 898 3719739 899 3743784 900 3767957 901 3792256 902 3816688 903 3841251 904 3865943 905 3890769 906 3915729 907 3940822 908 3966046 909 3991405 910 4016902 911 4042529 912 4068295 913 4094198 914 4120237 915 4146412 916 4172725 917 4199178 918 4225765 919 4252497 920 4279364 921 4306376 922 4333525 923 4360815 924 4388252 925 4415825 926 4443544 927 4471406 928 4499415 929 4527564 930 4555860 931 4584305 932 4612889 933 4641627 934 4670506 935 4699541 936 4728718 937 4758046 938 4787527 939 4817153 940 4846931 941 4876860 942 4906947 943 4937178 944 4967564 945 4998110 946 5028797 947 5059649 948 5090651 949 5121816 950 5153128 951 5184603 952 5216237 953 5248021 954 5279972 955 5312077 956 5344352 957 5376776 958 5409368 959 5442123 960 5475031 961 5508111 962 5541350 963 5574760 964 5608325 965 5642064 966 5675966 967 5710028 968 5744267 969 5778666 970 5813244 971 5847979 972 5882892 973 5917971 974 5953219 975 5988643 976 6024235 977 6060008 978 6095944 979 6132061 980 6168351 981 6204812 982 6241455 983 6278270 984 6315271 985 6352437 986 6389790 987 6427319 988 6465025 989 6502915 990 6540981 991 6579238 992 6617663 993 6656280 994 6695078 995 6734057 996 6773224 997 6812574 998 6852118 999 6891834 1000 6931749