0 1 1 1 2 1 3 1 4 1 5 2 6 1 7 3 8 1 9 1 10 2 11 6 12 1 13 9 14 3 15 2 16 1 17 17 18 1 19 23 20 2 21 4 22 7 23 40 24 1 25 7 26 10 27 1 28 3 29 87 30 2 31 111 32 1 33 17 34 25 35 21 36 1 37 219 38 34 39 34 40 2 41 336 42 4 43 413 44 7 45 2 46 73 47 614 48 1 49 87 50 7 51 103 52 10 53 1083 54 1 55 149 56 3 57 176 58 206 59 1850 60 2 61 2198 62 281 63 7 64 1 65 344 66 18 67 3630 68 25 69 479 70 22 71 5007 72 1 73 5861 74 725 75 13 76 34 77 881 78 36 79 9282 80 2 81 1 82 1311 83 12488 84 4 85 1597 86 1742 87 1841 88 7 89 19232 90 2 91 2445 92 78 93 2808 94 3052 95 3222 96 1 97 33439 98 97 99 47 100 7 101 43709 102 117 103 49871 104 10 105 60 106 6784 107 64671 108 1 109 73506 110 170 111 9298 112 3 113 94625 114 202 115 11989 116 230 117 111 118 14533 119 15384 120 2 121 17414 122 18581 123 19680 124 316 125 165 126 7 127 221265 128 1 129 28284 130 401 131 279516 132 18 133 35862 134 38125 135 2 136 25 137 394170 138 579 139 441250 140 22 141 57095 142 60582 143 64010 144 1 145 71730 146 76016 147 478 148 866 149 766262 150 13 151 853692 152 34 153 616 154 1086 155 125311 156 36 157 1175344 158 147818 159 155932 160 2 161 173756 162 1 163 1608014 164 1652 165 1040 166 227397 167 1975108 168 4 169 266420 170 2076 171 1350 172 2227 173 2675925 174 2418 175 1566 176 7 177 404687 178 426369 179 3605666 180 2 181 3977861 182 3271 183 550596 184 78 185 609470 186 3802 187 674307 188 4115 189 11 190 4372 191 6447003 192 1 193 7089299 194 957087 195 3587 196 97 197 8559069 198 48 199 9397474 200 7 201 1349792 202 1417500 203 1487720 204 117 205 1639032 206 1720392 207 5708 208 10 209 1986719 210 62 211 16298212 212 9783 213 2404094 214 2521230 215 2642938 216 1 217 2904333 218 3044496 219 3190278 220 170 221 3502954 222 13878 223 27810910 224 3 225 35 226 4418363 227 33121140 228 202 229 36123177 230 18291 231 13983 232 232 233 42917077 234 116 235 6668524 236 22465 237 7300071 238 23913 239 55416136 240 2 241 60299078 242 27489 243 1 244 29296 245 23092 246 31441 247 11416545 248 318 249 12471849 250 172 251 91477898 252 7 253 14869353 254 15535008 255 32846 256 1 257 116975172 258 46803 259 19309812 260 401 261 40355 262 21982235 263 149128391 264 18 265 25005441 266 60720 267 27238714 268 64639 269 189566161 270 2 271 205220288 272 25 273 60720 274 36661509 275 64970 276 584 277 259894960 278 43374397 279 74247 280 22 281 303759545 282 101433 283 328249663 284 108063 285 90567 286 114806 287 63057881 288 1 289 68474019 290 130528 291 74335237 292 138666 293 481628967 294 499 295 87536162 296 876 297 197 298 98886840 299 102973628 300 13 301 111642104 302 116236289 303 121009507 304 34 305 131129962 306 652 307 814393691 308 1097 309 153866209 310 241845 311 944043865 312 36 313 1016030162 314 187651277 315 193 316 290272 317 1176012119 318 308882 319 228509943 320 2 321 247143540 322 347899 323 267234807 324 1 325 324565 326 300347608 327 312235555 328 1684 329 337388083 330 1102 331 1947093861 332 469765 333 416013 334 409097756 335 425101643 336 4 337 2408365961 338 560996 339 495367125 340 2116 341 534569858 342 1435 343 563322 344 2271 345 599094 346 646096366 347 3417355260 348 2470 349 3662709662 350 1655 351 481 352 7 353 4204869720 354 895005 355 905745799 356 948339 357 857608 358 1012781488 359 5164194494 360 2 361 1131957063 362 1174608528 363 1024066 364 3350 365 1312058121 366 1263512 367 6772892496 368 78 369 1220851 370 1414920 371 1634979033 372 3906 373 8283364528 374 1586016 375 825 376 4237 377 2033930326 378 11 379 10113278821 380 4487 381 2350454441 382 2436727233 383 11541858454 384 1 385 1937844 386 2813392052 387 2053410 388 2348248 389 14052532822 390 3851 391 3363764755 392 97 393 3611859708 394 3742446573 395 3877581669 396 48 397 18223771491 398 4311879175 399 2885829 400 7 401 20731198708 402 3460757 403 5142097062 404 3656046 405 2 406 3859706 407 5915517465 408 117 409 26773685630 410 4307324 411 6800788452 412 4545875 413 7290151557 414 6182 415 7813468300 416 10 417 8373010561 418 5348642 419 36723296266 420 62 421 39100061431 422 9946615173 423 5621031 424 10182 425 5937571 426 6636100 427 11804419208 428 7001614 429 6621828 430 7383031 431 53373949919 432 1 433 56775073739 434 8216557 435 7793224 436 8661792 437 16578290931 438 9136797 439 68272721754 440 170 441 4319 442 10152883 443 77146303903 444 14528 445 21695616162 446 22433904170 447 23196470695 448 3 449 92563166927 450 35 451 26505430742 452 13207603 453 28326876617 454 29282468220 455 13312416 456 202 457 117776850169 458 33426525334 459 4985 460 19228 461 132740357102 462 15341 463 140891231740 464 232 465 17326918 466 43484855787 467 158659773825 468 116 469 47966362521 470 21063078 471 51199192022 472 23724 473 54642624228 474 23339762 475 22489372 476 25223 477 23692228 478 64261633545 479 225844849410 480 2 481 70800040930 482 73119408630 483 27666899 484 29121 485 80527873208 486 1 487 285034672876 488 31037 489 91545506902 490 25543 491 319968768174 492 33417 493 104018011909 494 38790565 495 10309 496 318 497 118130855228 498 42892411 499 402599630302 500 172 501 134092335970 502 138398362516 503 451268034861 504 7 505 152136300060 506 52392521 507 51000135 508 55058783 509 535034179285 510 36569 511 183689580483 512 1 513 17114 514 201760567786 515 208158739403 516 50126 517 221550782513 518 70549625 519 235776957524 520 401 521 749695337946 522 45138 523 792729981581 524 81775266 525 21323 526 292890610824 527 302074158163 528 18 529 321286879710 530 94719424 531 92776260 532 65350 533 363333428964 534 104423275 535 386312570026 536 69607 537 410699529218 538 423446875883 539 112942759 540 2 541 1303426263832 542 478386390602 543 493167206734 544 25 545 524070443160 546 68407 547 1535372736248 548 146567446 549 144143816 550 73216 551 628486642981 552 584 553 667583592858 554 688007621303 555 166701652 556 177580037 557 2012955556495 558 83965 559 799576963327 560 22 561 192648739 562 874751763108 563 2365170119166 564 110457 565 956772281197 566 985736671971 567 18 568 117819 569 2776455046698 570 102809 571 2928278002633 572 125201 573 1213719781258 574 272378576 575 269265291 576 1 577 3433343526298 578 299327576 579 1449248169495 580 142926 581 1537203841075 582 328816389 583 1630337367288 584 151882 585 62554 586 1780397435387 587 4467237769489 588 499 589 1943844836040 590 396482131 591 2060815030148 592 876 593 5225526104413 594 198 595 431591343 596 455884579 597 2454269735376 598 477506399 599 6107331049325 600 13 601 6431971891087 602 523867175 603 520205600 604 548603044 605 544970782 606 574530760 607 7508991694989 608 34 609 597942309 610 629908226 611 3677533243235 612 652 613 8759161064079 614 4008089812662 615 686865283 616 1097 617 9701844024362 618 756689803 619 10209209398535 620 268547 621 116320 622 5037188364147 623 5182637340072 624 36 625 124384 626 5643921539581 627 904666924 628 950159031 629 6145043657370 630 198 631 13836238489109 632 323931 633 6880986135454 634 7077966673036 635 7280428598004 636 345626 637 1135934201 638 1191298643 639 1188659180 640 2 641 17783239931613 642 1303490932 643 18693876777058 644 390022 645 1361313273 646 1425869691 647 20652263629127 648 1 649 10781033915175 650 378225 651 1558140283 652 1630643161 653 23966295724829 654 1705077826 655 12740461642360 656 1684 657 1782409040 658 1863811145 659 27791703929926 660 1102 661 29193296710728 662 15466427389218 663 2037809220 664 531449 665 2130583975 666 488258 667 17752980519395 668 2326142555 669 18756965203974 670 2431030596 671 19816142642136 672 4 673 39153077902249 674 21514889302293 675 171 676 637684 677 43150687924574 678 2898795991 679 24666118890262 680 2118 681 26048688695993 682 3164227983 683 49896404240745 684 1435 685 29043872622514 686 665149 687 30664679111174 688 2271 689 32373443525830 690 709199 691 60494419065449 692 3935464556 693 383870 694 37061223994749 695 38075109249288 696 2472 697 40184569916640 698 41281562378240 699 42407704104382 700 1655 701 76832052552686 702 490 703 47219130930077 704 7 705 5124668076 706 51172661432330 707 52560795096363 708 1031095 709 92903223548632 710 5807210290 711 5834107163 712 1094239 713 61693262779045 714 1024253 715 6358962031 716 6604908377 717 68621954506439 718 70469266594666 719 117608544918460 720 2 721 76306723819362 722 7508584404 723 80457379016801 724 7835524540 725 7879900117 726 1228641 727 141844925043019 728 3354 729 1 730 8901965979 731 99373176694987 732 1470450 733 163128057231579 734 107530471666187 735 705586 736 78 737 116339085754432 738 1471489 739 187489152292764 740 1650935 741 11073898339 742 11474003434 743 205649453322277 744 3910 745 143409907704921 746 147198127366266 747 12570138477 748 1858143 749 159157560832516 750 843 751 247219168888925 752 4239 753 176586517472895 754 14762178026 755 185985363233591 756 11 757 283626678461325 758 201004619783762 759 16173825699 760 4493 761 310729228398457 762 17445317178 763 228703906062360 764 18186877581 765 1199040 766 247074526353689 767 253511984071622 768 1 769 372663112619435 770 2362805 771 280937412979136 772 21471038424 773 407959884032354 774 2509547 775 22570590876 776 2783428 777 23525611431 778 336052917028768 779 344741611346152 780 3851 781 362781333268822 782 26394493606 783 1502688 784 97 785 401665329929774 786 28656951356 787 558874054265503 788 29857934849 789 444604376218769 790 31107401933 791 467721593901100 792 48 793 492009974082057 794 504611310353152 795 34083548315 796 35169570550 797 698477916532171 798 3560329 799 572494282441876 800 7 801 38533582197 802 617417800718355 803 633142984459885 804 4155779 805 41808518289 806 43113167080 807 700045081274511 808 4397953 809 910956412837564 810 2 811 951988626546960 812 4648729 813 813512894008405 814 50699418270 815 855181302631977 816 117 817 898930086735680 818 921616075058466 819 2609560 820 5209098 821 1185557675132166 822 59578681869 823 1238527221791851 824 5504878 825 2984263 826 64567872356 827 1351439869617259 828 6187 829 1411579074734150 830 69963393922 831 1272561215531920 832 10 833 73625909111 834 75795893789 835 1404684977903175 836 6512210 837 3568013 838 1512474733180032 839 1753396986042209 840 62 841 1628324943427951 842 1668833249281641 843 1710324852456543 844 92524300106 845 93581960076 846 7070809 847 97383096482 848 10196 849 1981266348813429 850 7480593 851 2080567395454230 852 8143288 853 2369806010824137 854 112825693699 855 4478734 856 8607027 857 2581547949682147 858 8370658 859 2694193383616078 860 9088455 861 128534734682 862 2719952171032007 863 2933972637854446 864 1 865 2925328464617701 866 2997094817841152 867 144677901622 868 10156145 869 3222866592076243 870 9900572 871 3382521637990602 872 10721758 873 162787300068 874 167243401097 875 6007727 876 11335936 877 3947542528078787 878 4004506296935799 879 4102023892457146 880 170 881 4294796706216035 882 4370 883 4479368928403790 884 12637362 885 205860713683 886 4852661712072855 887 4871899433253987 888 14562 889 5214004064205492 890 228472750460 891 1605 892 237514629709 893 5736931234757839 894 246906130083 895 6017271229556974 896 3 897 259951324908 898 6463041852355545 899 6618681095144810 900 35 901 6941023726922491 902 288220018822 903 291955915656 904 16600005 905 7632385869463758 906 311327948388 907 7392413764411863 908 323549488009 909 327784543151 910 17198008 911 8030528672143249 912 202 913 9222878888196294 914 9443160819481314 915 367880803473 916 377277754169 917 10135310283724396 918 5157 919 9471195582169338 920 19278 921 11135762987639786 922 11400583699564621 923 11671556148215187 924 15357 925 445556012904 926 12522795400113686 927 462905630095 928 232 929 11628085044316632 930 22577372 931 499598521712 932 512055613398 933 14751923121834192 934 15100493015644837 935 539120936022 936 116 937 13690469846901122 938 573846137704 939 16967731130166709 940 26924598 941 14850830190435401 942 619014336108 943 18622356993719968 944 23782 945 795 946 667639826053 947 16772485454952436 948 29948717 949 21403926604089481 950 29547691 951 22418401697683021 952 25291 953 18934918156699593 954 31193326 955 24590355533589995 956 806070931364 957 817305297145 958 26353040662706637 959 26967607953523493 960 2 961 28239073205661348 962 902161538458 963 914813515954 964 936604501911 965 30960301965709529 966 36617112 967 25087526755677506 968 29215 969 1023624016977 970 1047810199131 971 27176568418025575 972 1 973 37193864714988480 974 38054577525683571 975 25107029 976 31123 977 30630565726175256 978 1216293660632 979 42658921099601537 980 25594 981 1280383895816 982 45678506294902203 983 34509857434776495 984 33531 985 48906811846036088 986 1411084430805 987 1431312577859 988 50732858 989 53560379840090045 990 10667 991 40432337968115894 992 318 993 58646153788832837 994 1636169523333 995 61363231169519590 996 56315031 997 45511514714330818 998 65671182523272674 999 34996050 1000 172