0 1 1 1 2 1 3 1 4 1 5 2 6 1 7 2 8 1 9 1 10 2 11 1 12 1 13 2 14 2 15 2 16 1 17 2 18 1 19 3 20 2 21 2 22 1 23 5 24 1 25 5 26 2 27 1 28 2 29 7 30 2 31 9 32 1 33 4 34 6 35 9 36 1 37 11 38 6 39 10 40 2 41 14 42 2 43 15 44 1 45 2 46 12 47 19 48 1 49 18 50 5 51 16 52 2 53 26 54 1 55 24 56 2 57 23 58 26 59 35 60 2 61 39 62 31 63 3 64 1 65 40 66 4 67 50 68 6 69 49 70 9 71 61 72 1 73 67 74 68 75 7 76 6 77 70 78 10 79 87 80 2 81 1 82 93 83 102 84 2 85 107 86 116 87 120 88 1 89 130 90 2 91 144 92 14 93 162 94 172 95 178 96 1 97 178 98 20 99 10 100 5 101 204 102 20 103 224 104 2 105 19 106 295 107 257 108 1 109 278 110 30 111 362 112 2 113 320 114 26 115 437 116 29 117 27 118 497 119 521 120 2 121 566 122 590 123 609 124 33 125 43 126 3 127 522 128 1 129 789 130 49 131 595 132 4 133 922 134 962 135 2 136 6 137 724 138 62 139 776 140 9 141 1271 142 1319 143 1377 144 1 145 1487 146 1544 147 69 148 85 149 1064 150 7 151 1136 152 6 153 88 154 88 155 2183 156 10 157 1364 158 2432 159 2525 160 2 161 2727 162 1 163 1634 164 129 165 129 166 3264 167 1836 168 2 169 3651 170 164 171 140 172 166 173 2192 174 169 175 178 176 1 177 4853 178 5028 179 2601 180 2 181 2761 182 225 183 5988 184 14 185 6411 186 237 187 6877 188 269 189 4 190 279 191 3645 192 1 193 3863 194 8743 195 313 196 20 197 4294 198 10 199 4549 200 5 201 11051 202 11422 203 11822 204 20 205 12624 206 13046 207 414 208 2 209 14389 210 19 211 6262 212 508 213 16400 214 16933 215 17506 216 1 217 18667 218 19266 219 19897 220 30 221 21212 222 645 223 8558 224 2 225 11 226 24873 227 9453 228 26 229 9964 230 822 231 780 232 30 233 11001 234 27 235 32929 236 918 237 35044 238 980 239 12774 240 2 241 13438 242 1098 243 1 244 1113 245 1175 246 1169 247 47568 248 33 249 50529 250 43 251 17122 252 3 253 56978 254 58731 255 1482 256 1 257 19775 258 1617 259 68128 260 49 261 1682 262 74441 263 22800 264 4 265 81306 266 1945 267 86192 268 2048 269 26237 270 2 271 27521 272 6 273 2289 274 105611 275 2430 276 64 277 31606 278 118462 279 2605 280 9 281 34597 282 2861 283 36254 284 2990 285 3071 286 3112 287 152999 288 1 289 161881 290 3508 291 171181 292 3631 293 45371 294 71 295 191420 296 87 297 32 298 208114 299 213945 300 7 301 226093 302 232421 303 238879 304 6 305 252321 306 92 307 61826 308 90 309 281510 310 5525 311 67379 312 10 313 70433 314 322424 315 49 316 6236 317 76683 318 6575 319 368889 320 2 321 389180 322 7188 323 410622 324 1 325 7687 326 444679 327 456654 328 132 329 481454 330 135 331 103287 332 9007 333 9145 334 549300 335 563921 336 2 337 117082 338 10289 339 626036 340 171 341 659485 342 145 343 11386 344 169 345 11928 346 750747 347 143830 348 175 349 149946 350 182 351 84 352 1 353 162579 354 14410 355 945717 356 15108 357 15424 358 1020881 359 183551 360 2 361 1101516 362 1129733 363 17534 364 234 365 1218408 366 18623 367 215566 368 14 369 19806 370 20410 371 1416369 372 247 373 242826 374 22119 375 129 376 285 377 1644208 378 4 379 273231 380 292 381 1815245 382 1860554 383 295320 384 1 385 27878 386 2052649 387 28982 388 29649 389 331765 390 326 391 2319322 392 20 393 2435090 394 2494940 395 2556244 396 10 397 387152 398 2748622 399 36963 400 5 401 417658 402 39439 403 3100229 404 41056 405 2 406 42694 407 3412136 408 20 409 486245 410 46534 411 3753390 412 48312 413 3936074 414 438 415 4127105 416 2 417 4327147 418 54446 419 586167 420 19 421 608603 422 4867988 423 60046 424 538 425 62698 426 63654 427 5472638 428 66457 429 67516 430 69179 431 731698 432 1 433 759378 434 74681 435 76257 436 77574 437 6903258 438 80794 439 847188 440 30 441 381 442 87364 443 910602 444 686 445 8298027 446 8490024 447 8686286 448 2 449 1014643 450 11 451 9515632 452 106123 453 9958356 454 10186926 455 112481 456 26 457 1171154 458 11152051 459 454 460 894 461 1257010 462 840 463 1302825 464 30 465 136008 466 13350534 467 1397631 468 27 469 14276936 470 149693 471 14927969 472 1006 473 15607492 474 161033 475 164380 476 1064 477 170572 478 17438579 479 1724253 480 2 481 18633424 482 19048778 483 190829 484 1195 485 20348255 486 1 487 1980967 488 1206 489 22213988 490 1296 491 2121455 492 1281 493 24242172 494 234186 495 812 496 33 497 26445983 498 252144 499 2433127 500 43 501 28841410 502 29471829 503 2603598 504 3 505 31442942 506 292112 507 297535 508 303144 509 2881497 510 1644 511 35769301 512 1 513 1017 514 38141047 515 38964473 516 1794 517 40662393 518 363698 519 42430405 520 49 521 3523070 522 1867 523 3643304 524 405131 525 1267 526 49218323 527 50268819 528 4 529 52434798 530 451714 531 459141 532 2170 533 57036696 534 484494 535 59480611 536 2290 537 62024904 538 63335894 539 529931 540 2 541 4900916 542 68848486 543 70296411 544 6 545 73280627 546 2581 547 5404079 548 621898 549 632395 550 2751 551 82981224 552 64 553 86478752 554 88280157 555 703452 556 715470 557 6351011 558 2929 559 97839804 560 9 561 780687 562 104044279 563 6993095 564 3236 565 110623992 566 112904194 567 6 568 3378 569 7695807 570 3484 571 7945947 572 3526 573 130176914 574 978972 575 996825 576 1 577 8738436 578 1049546 579 146971685 580 4037 581 153017764 582 1123942 583 159301897 584 4106 585 2839 586 169195543 587 10225488 588 71 589 179675568 590 1289607 591 187004193 592 87 593 11230572 594 32 595 1404072 596 1427649 597 210754418 598 1477222 599 12328072 600 7 601 12717945 602 1581197 603 1607541 604 1634869 605 1663674 606 1690619 607 13952032 608 6 609 1778332 610 1809528 611 277945926 612 92 613 15298808 614 294807440 615 1967590 616 90 617 16261123 618 2068578 619 16767497 620 6423 621 4529 622 344712406 623 351493597 624 10 625 4856 626 372611693 627 2403480 628 2443944 629 394945348 630 49 631 20114137 632 7296 633 426733776 634 435056373 635 443535048 636 7759 637 2836165 638 2883495 639 2930255 640 2 641 23373103 642 3079045 643 24086483 644 8433 645 3234834 646 3287775 647 25564108 648 1 649 580246046 650 9089 651 3567569 652 3627312 653 27948834 654 3746514 655 650496132 656 132 657 3934584 658 3999213 659 30542630 660 135 661 31460518 662 742803775 663 4336504 664 10760 665 4480489 666 10958 667 816311145 668 4702362 669 847632389 670 4856652 671 880107415 672 2 673 37514579 674 931069250 675 29 676 12441 677 39761874 678 5521674 679 1022373508 680 172 681 1061257304 682 5887348 683 43381767 684 145 685 1143333044 686 13761 687 1186625733 688 169 689 1231493296 690 14470 691 48700546 692 6904124 693 10874 694 1350924324 695 1376112056 696 176 697 1427848790 698 1454412820 699 1481452099 700 182 701 56207579 702 84 703 1594532212 704 1 705 8478331 706 1684750848 707 1715899489 708 17595 709 63002471 710 9172227 711 9314746 712 18569 713 1914756698 714 18874 715 9919117 716 10074153 717 2059465711 718 2097256387 719 72578331 720 2 721 2214671219 722 11063732 723 2296435482 724 11412008 725 11592764 726 21711 727 81231014 728 236 729 1 730 12526916 731 2653540213 732 23103 733 88348389 734 2800774239 735 18265 736 14 737 2955859573 738 24589 739 96054196 740 25430 741 14842344 742 15074504 743 101533364 744 247 745 3410951655 746 3472372731 747 16276131 748 27705 749 3663099044 750 129 751 113422641 752 286 753 3933167768 754 18114597 755 4075297344 756 4 757 123188093 758 4297805420 759 19547494 760 294 761 130126307 762 20460608 763 4694912259 764 21091624 765 26013 766 4949916113 767 5037843708 768 1 769 145167325 770 35324 771 5404845464 772 23806676 773 153276249 774 36774 775 24909264 776 37774 777 25668781 778 6110009825 779 6217719581 780 326 781 6438656109 782 27673215 783 31561 784 20 785 6903455779 786 29379468 787 185244203 788 30275127 789 7400543382 790 31194412 791 7661859649 792 10 793 7932056344 794 8070578712 795 33608234 796 34110907 797 211833279 798 47603 799 8798938642 800 5 801 36740760 802 9265973948 803 9426899550 804 50984 805 38988843 806 39568034 807 10097971384 808 53323 809 248561262 810 2 811 255259466 812 55483 813 11191742180 814 44528337 815 11581100052 816 20 817 11983509357 818 12189737767 819 47782 820 61054 821 291299283 822 50084046 823 299089910 824 63128 825 51426 826 53105781 827 315208173 828 440 829 323604661 830 56305979 831 15203071636 832 2 833 58823312 834 59682510 835 16266826456 836 71929 837 58403 838 17111444663 839 368747854 840 19 841 17998312465 842 18303675429 843 18614035240 844 69015818 845 70026520 846 79892 847 72080775 848 543 849 20585721627 850 83801 851 21286673106 852 84894 853 442185731 854 79742032 855 71611 856 89189 857 465569854 858 90178 859 477739387 860 92667 861 88183826 862 25573478253 863 502912788 864 1 865 26880348565 866 27330130778 867 96104076 868 100667 869 28723534831 870 102871 871 29690344939 872 104638 873 104702979 874 106206511 875 89022 876 109459 877 601489256 878 33327998575 879 33881585929 880 30 881 632837438 882 383 883 649138960 884 118638 885 124179574 886 38013238300 887 682847693 888 690 889 39929314596 890 133288935 891 140 892 137106614 893 42629767653 894 141025548 895 44045374087 896 2 897 147118876 898 46254326071 899 47014152455 900 11 901 48570157560 902 157840280 903 160068430 904 146417 905 51832872290 906 166945996 907 878249473 908 171697217 909 174111856 910 155968 911 923215324 912 26 913 59005797647 914 59967206061 915 189346152 916 192004239 917 62943179880 918 458 919 1019958823 920 900 921 67134091562 922 68223251483 923 69329489315 924 842 925 217624782 926 72753250785 927 223743395 928 30 929 1154427195 930 190502 931 236495341 932 239794493 933 81389965205 934 82702002749 935 249951404 936 27 937 1274114494 938 260517689 939 89575072740 940 211589 941 1338235966 942 275276118 943 95468285082 944 1011 945 143 946 290844328 947 1440312937 948 227822 949 105016991765 950 233153 951 108400457047 952 1070 953 1549803663 954 242321 955 115486668641 956 333569678 957 338159752 958 121093404716 959 123020168499 960 2 961 126963076247 962 362050208 963 367012863 964 372048648 965 135219023590 966 273616 967 1837100999 968 1206 969 398229229 970 403686658 971 1928028390 972 1 973 153317794977 974 155738646922 975 256301 976 1215 977 2072633998 978 449914769 979 168408652434 980 1305 981 468534552 982 176483647535 983 2227574471 984 1289 985 184932831478 986 501244324 987 508042652 988 340625 989 196809587703 990 818 991 2451525916 992 33 993 209423335587 994 558197086 995 216020256579 996 368667 997 2633390186 998 226294316010 999 327265 1000 43