1 1 2 2 3 3 4 1 5 5 6 3 7 7 8 9 9 13 10 17 11 2 12 19 13 39 14 6 15 35 16 72 17 21 18 59 19 141 20 55 21 1 22 107 23 266 24 132 25 7 26 187 27 511 28 300 29 26 30 351 31 952 32 660 33 85 34 631 35 1827 36 1395 37 240 38 3 39 1181 40 3459 41 2901 42 636 43 15 44 2191 45 6595 46 5977 47 1554 48 67 49 4115 50 12604 51 12123 52 3698 53 228 54 7711 55 24173 56 24504 57 8434 58 711 59 3 60 14601 61 46383 62 49188 63 18876 64 2001 65 23 66 27595 67 89311 68 98524 69 41246 70 5363 71 105 72 52487 73 172148 74 196604 75 89029 76 13612 77 408 78 99879 79 332531 80 391839 81 189570 82 33362 83 1394 84 1 85 190745 86 643241 87 779361 88 400135 89 79352 90 4299 91 19 92 364723 93 1246081 94 1549197 95 837404 96 184351 97 12444 98 104 99 699251 100 2416788 101 3075903 102 1742254 103 419872 104 34066 105 474 106 1342183 107 4693301 108 6104766 109 3604420 110 941291 111 89445 112 1810 113 2581427 114 9123652 115 12108519 116 7425932 117 2081947 118 226707 119 6242 120 6 121 4971067 122 17754097 123 24010973 124 15240687 125 4553317 126 558951 127 19712 128 60 129 9587579 130 34580216 131 47597203 132 31183962 133 9864682 134 1345063 135 58687 136 336 137 18512791 138 67411453 139 94338968 140 63632493 141 21198086 142 3174284 143 165854 144 1527 145 35792567 146 131518270 147 186949229 148 129552664 149 45237648 150 7364135 151 450413 152 5986 153 69273667 154 256783457 155 370447281 156 263233060 157 95959253 158 16841938 159 1181959 160 21194 161 15 162 134219795 163 501710554 164 733997070 165 533938517 166 202493614 167 38038670 168 3015896 169 69403 170 129 171 260301175 172 980907577 173 1454297578 174 1081386345 175 425350256 176 84998429 177 7511401 178 213757 179 778 180 505294127 181 1918996670 182 2881403029 183 2187228715 184 889904987 185 188148182 186 18328392 187 626842 188 3648 189 981706831 190 3756443155 191 5709011357 192 4418696582 193 1855223998 194 413074918 195 43932870 196 1764488 197 14985 198 1908881899 199 7357356724 200 11311650719 201 8917446867 202 3855523056 203 900327217 204 103696073 205 4800454 206 55339 207 20 208 3714566311 209 14417722381 210 22413407670 211 17979611690 212 7990027301 213 1949796578 214 241469653 215 12685709 216 189243 217 200 218 7233642929 219 28267636859 220 44412856896 221 36220732648 222 16516610656 223 4198505551 224 555658754 225 32700181 226 607704 227 1294 228 14096303343 229 55448474621 230 88010317600 231 72913397496 232 34065060315 233 8994707139 234 1265294180 235 82489418 236 1856295 237 6537 238 27487816991 239 108814540724 240 174415212818 241 146677417455 242 70114837360 243 19181848576 244 2854462316 245 204213973 246 5435137 247 28538 248 53634713551 249 213634909987 250 345671938621 251 294885165570 252 144047442086 253 40738527296 254 6386198059 255 497259092 256 15361946 257 111553 258 15 259 104715443851 260 419601318342 261 685131988148 262 592517806818 263 295440412449 264 86198990270 265 14181496886 266 1193279849 267 42116998 268 401728 269 213 270 204560302843 271 824466041455 272 1358052623378 273 1189955020835 274 605016074274 275 181774400885 276 31281603023 277 2826603347 278 112484561 279 1354955 280 1548 281 399822505523 282 1620587625374 283 2692105693552 284 2388690889069 285 1237239961551 286 382145249596 287 68584591051 288 6618549472 289 293615716 290 4332580 291 8724 292 781874936815 293 3186611212247 294 5337057219417 295 4792994746703 296 2526860917680 297 801136416758 298 149548648254 299 15337475819 300 751178568 301 13250924 302 41231 303 1529755490573 304 6268099889871 305 10581479904589 306 9613623528875 307 5154593079747 308 1675211408883 309 324469525064 310 35212143198 311 1887915785 312 39029068 313 173173 314 6 315 2994414645859 316 12333514798965 317 20981007512501 318 19275884878639 319 10503481773060 320 3494698790901 321 700797240877 322 80162109975 323 4670464729 324 111298193 325 663821 326 144 327 5864062367251 328 24275946223976 329 41604653149871 330 38636796776691 331 21381309419099 332 7274587945071 333 1507325365272 334 181104118414 335 11392012126 336 308605734 337 2370519 338 1304 339 11488774559635 340 47796754355079 341 82507483707276 342 77420993504177 343 43484042768774 344 15112582630494 345 3229743462719 346 406322027748 347 27436752354 348 834947458 349 7986458 350 8484 351 22517998808027 352 94134425390808 353 163636691631417 354 155094854559229 355 88358746840465 356 31337624346027 357 6896187509026 358 905860304589 359 65327753958 360 2210589218 361 25643857 362 44691 363 44152937528383 364 185447746579871 365 324566689557231 366 310617754381144 367 179398889041594 368 64870839669109 369 14677414553826 370 2007869105273 371 153945893513 372 5741285904 373 79041604 374 205171 375 1 376 86607686432615 377 365437507005304 378 643817809508634 379 621947552810577 380 363969214383454 381 134073265917441 382 31145582678712 383 4426919676861 384 359381841228 385 14657330621 386 235250935 387 848811 388 55 389 169947155749831 390 720309031908329 391 1277196279156558 392 1245051903090879 393 737914711736885 394 276689197713141 395 65909180900676 396 9712825446291 397 831811441725 398 36847799581 399 679184201 400 3241668 401 731 402 333599974893065 403 1420151654319551 404 2533889544533460 405 2491921087107654 406 1495079552532094 407 570220983488887 408 139118383207926 409 21214528561213 410 1910269144076 411 91356048924 412 1909295790 413 11602555 414 5797 415 655069036708591 416 2800637279706033 417 5027508492714896 418 4986554548669509 419 3027312862740804 420 1173639857807122 421 292948016494342 422 46143852543213 423 4355611803049 424 223668502482 425 5242390800 426 39365657 427 35486 428 1286742755471399 429 5524355786839140 430 9975914494602160 431 9976819349430135 432 6126351438806328 433 2412700056743903 434 615509731268204 435 99981784609410 436 9866004041561 437 541393431843 438 14095869567 439 127667935 440 182383 441 2528336632928151 442 10899475309211043 443 19796437415804005 444 19957869882012301 445 12391202040631830 446 4954293056863758 447 1290571292840963 448 215861477131651 449 22212451836968 450 1296881836074 451 37197636793 452 398364950 453 829440 454 9 455 4969489253251427 456 21509258295308514 457 39287590762057532 458 39918266354153504 459 25049900313918927 460 10162490945686020 461 2700787390916313 462 464500039397356 463 49729810711787 464 3077184198902 465 96520709938 466 1202111872 467 3433537 468 243 469 9770521225481755 470 42455899597601763 471 77975358838229014 472 79830533428086250 473 50616554355250665 474 20825072584107183 475 5641746800319735 476 996440983331867 477 110760196307131 478 7237939383085 479 246667628747 480 3522786455 481 13195472 482 2622 483 19215358428046175 484 83818611043405442 485 154772062998763407 486 159628479984211057 487 102231596345471046 488 42634998871231472 489 11765231384427913 490 2131387734281114 491 245505239096060 492 16888433809063 493 621733068951 494 10059880633 495 47711377 496 19778 497 37800705069076951 498 165512135891039467 499 307227813016616829 500 319153420328357435 501 206392902858754916 502 87209311766027808 503 24496037740601980 504 4546740708114451 505 541745980583608 506 39115507137890 507 1547502307563 508 28074156967 509 163952888 510 118223 511 74382032589917285 512 326891405123979815 513 609903053822570481 514 638028243804153964 515 416515981239128089 516 178237058246693367 517 50926148055418046 518 9674742414129890 519 1190480670350111 520 89978235051439 521 3807722491314 522 76749716063 523 539487781 524 606307 525 146402730743793239 526 645741748193623631 527 1210857265909552943 528 1275365940315489119 529 840243891394154999 530 363991904368004279 531 105723921643694747 532 20537538850415075 533 2605926949370635 534 205671481516525 535 9270898033184 536 205966918188 537 1710048952 538 2772352 539 36 540 288230376218822675 541 1275831964687252600 542 2404121992634170585 543 2549102071145111122 544 1694433984314008383 545 742784028046457089 546 219193673029962037 547 43500045771955413 548 5683632252139913 549 467365179435667 550 22354768315084 551 543549163742 552 5246376157 553 11604639 554 702 555 567592125344909791 556 2521186649819609189 557 4773654594108476126 558 5094480558417836375 559 3415841634089390160 560 1514703723152640653 561 453876048697156541 562 91943451778953813 563 12354194634894559 564 1056240845653475 565 53424374503358 566 1412760624310 567 15639667412 568 45228663 569 7191 570 1117984489446008099 571 4983003412298165496 572 9479293225294924405 573 10180648313172862924 574 6883862875844090328 575 3086761655391328476 576 938708567688344924 577 193952113873505433 578 26768243662222966 579 2374957432430108 580 126626355729126 581 3621345809837 582 45447426270 583 166201545 584 53295 585 2202596307308603179 586 9850309873555886073 587 18824824394586263351 588 20343055795637833598 589 13868682574470265359 590 6286423184333418675 591 1939260416527456256 592 408375386261522996 593 57826481678128709 594 5314741547806054 595 297843777784811 596 9165485045106 597 129086728705 598 581143315 599 320277 600 4340410370537249375 601 19475072011027498608 602 37386555565328749246 603 40646615833916535184 604 27932727925595463819 605 12795081810728735427 606 4002016686272513998 607 858343046649048073 608 124569769757216038 609 11840661964108898 610 695618137819774 611 22928608194627 612 359204178446 613 1947438170 614 1663245 615 8555011744329310567 616 38510287217212675433 617 74255574191903696670 618 81208615598894980315 619 56243564375777991757 620 26027613588623882031 621 8250548691563159920 622 1801109452686107324 623 267638668537983952 624 26269979569895663 625 1613936348986501 626 56746435268539 627 981171678324 628 6289471472 629 7737304 630 84 631 16865594582168158775 632 76162478090948800894 633 147492959798592189343 634 162237503525305760343 635 113219037399035372198 636 52916303803956804290 637 16992999840380829581 638 3773424910150428455 639 573589320653756832 640 58055771232417959 641 3721603093149347 642 139058176428115 643 2635312822660 644 19665712489 645 33018943 646 1488 647 33256101992039755027 648 150650366251595030669 649 292982507131461493043 650 324095968469113218486 651 227855043611136192349 652 107527555671538272508 653 34967224510376813191 654 7893751409438349271 655 1226393589768237249 656 127830843044693875 657 8532553397390875 658 337654374328163 659 6970241982962 660 59754160070 661 131370317 662 15369 663 65588423374144427519 664 298031659989352163796 665 582022549617276681414 666 647397325115608950693 667 458453707309334787210 668 218391485321084657922 669 71891141489244900018 670 16489842379534216013 671 2616322907253064384 672 280494802583024212 673 19457840946769715 674 812932508203587 675 18178471365325 676 176986175204 677 493104279 678 115557 679 129379903640264252431 680 589679503112606542701 681 1156285836603824090414 682 1293137280254515447099 683 922220480350747045586 684 443350455708691489431 685 147683053470725787011 686 34400581053758972858 687 5569771220117112159 688 613479000625669904 689 44149345530618690 690 1941792655529255 691 46801476908394 692 512343329381 693 1761706707 694 711675 695 255263053129946213627 696 1166888836645325750964 697 2297298539328511900777 698 2582832742157750863118 699 1854731099130156558709 700 899628918312095737494 701 303140393929527422731 702 71673736768336418503 703 11833576553070578079 704 1337643350061869521 705 99701723397114627 706 4604183821691833 707 119068458400122 708 1452793811329 709 6032303637 710 3792321 711 503719091506096385999 712 2309410968177029076447 713 4564530035954505487463 714 5158544946893348884332 715 3729394127764767243991 716 1824707030903703935186 717 621771129816662790168 718 149150997875223517488 719 25094123486424602176 720 2908175652132525062 721 224157575530998065 722 10842195602823766 723 299614634370238 724 4042995035331 725 19905056151 726 18122795 727 126 728 994182417449857925987 729 4571195253150408335828 730 9069861960304669349027 731 10302407351725216482806 732 7497400661248402721586 733 3699512958533035747037 734 1274399639149932024909 735 310019641971283980187 736 53118638303557872223 737 6305346778943953831 738 501868661571005095 739 25368259935547468 740 746295965469455 741 11060724026365 742 63577829703 743 79435667 744 2394 745 1962541914958813595479 746 9049273360451231325913 747 18023155943765373572500 748 20574627304511533619050 749 15069609844309619840079 750 7497652835229037293343 751 2610254880489964223325 752 643683907025982715445 753 112248213446333448251 754 13635426228445560389 755 1119224347440486758 756 58999721459220620 757 1841440931509402 758 29790545099516 759 197287352547 760 324530725 761 25794 762 3874762242361630560583 763 17916437643777542482262 764 35816747468847936716983 765 41087348887883298421101 766 30284170045629742834223 767 15189473510491180883241 768 5342879666393775973376 769 1335052850963726467771 770 236813054563534634558 771 29414308940972597684 772 2486743618899373691 773 136444763911022053 774 4503900378935376 775 79094278026553 776 596587520417 777 1250185498 778 202902 779 7651429238067273257635 780 35476626741129100078417 781 71181344027297856981903 782 82048037874407312196499 783 60849225269114926005696 784 30761221137455532550907 785 10929374510006233044463 786 2766223285767942062556 787 498837676195074968713 788 63304328715109107894 789 5505803350525616173 790 313877110129531315 791 10926031787476043 792 207241303539064 793 1762604436232 794 4581521925 795 1301109 796 15111572745196608608735 797 70256159647262337905552 798 141472021103842504673184 799 163837459669906583924513 800 122242798988187912007698 801 62275085815805558207215 802 22343653370551919536079 803 5726091859989645933879 804 1049232602706375306545 805 135938927861121914979 806 12149784583265533241 807 718446392126063114 808 26303486481804292 809 536426843403656 810 5099213460281 811 16081864986 812 7205139 813 29850020237398254541371 814 139147914655255045591231 815 281189354197005022132216 816 327147847186694339615732 817 245540618999629942864694 818 126032080908110388419655 819 45652323635860939713563 820 11842131033744841450556 821 2203802802646703147170 822 291297885881312310824 823 26727048668550640546 824 1636764677100739171 825 62871628726426468 826 1372900934933461 827 14472669741718 828 54366745708 829 35691966 830 126 831 58971991200740435635127 832 275624630509749671375390 833 558921411709539672045757 834 653223284271955089632170 835 493126168312045865539221 836 254982076584355097132112 837 93224843346383349231791 838 24469155359707371118995 839 4622636674021304586883 840 622957046574243387533 841 58619058513991688461 842 3712365042297857343 843 149273014048714021 844 3477072220638417 845 40365729513552 846 177799456753 847 161855928 848 2898 849 116522970565265462622283 850 546018345768680870039629 851 1111030032387301564187855 852 1304267875384475492582195 853 990216271453497599147844 854 515709854878374354166998 855 190269942746116580571346 856 50517488642423011844760 857 9683866850412194778803 858 1329681004862705875777 859 128202930638624223353 860 8384829201348649308 861 352185223198923476 862 8720681556906600 863 110796874019748 864 564577339772 865 682910901 866 34056 867 230271584688553159320639 868 1081790674599276213126656 869 2208633507918023182369212 870 2604115618637224369507337 871 1988116809221215790670617 872 1042734167148057766356420 873 388139292714179261579533 874 104210949547774527949098 875 20261623802419064712390 876 2832983647147121772377 877 279633800439092302870 878 18863203484765594645 879 826014003330411364 880 21673812568368647 881 299674456123885 882 1746014391529 883 2712804489 884 287700 885 455125014443154512836735 886 2143507256727262658017461 887 4390803052310078653420460 888 5199274888627985733769988 889 3991130780004051831831114 890 2107749873249107611291279 891 791393690007882137643590 892 214806832345643318560473 893 42343718120065068979869 894 6025375402785511158256 895 608374683040286544177 896 42277148357264893447 897 1926549142355876777 898 53410626309499726 899 799600570304843 900 5272731115155 901 10237600480 902 1954986 903 899665726224942596211833 904 4247676006458031391114107 905 8729439179674543895415652 906 10380422616432465968233447 907 8011143553495383166879221 908 4259380893928390053864188 909 1612847477477358950963029 910 442445191274989696308675 911 88392334888621400526996 912 12793858262058322737620 913 1320370175262956075262 914 94416886564095993950 915 4469791039528904230 916 130575992988082781 917 2106868436695126 918 15583170153681 919 36961045550 920 11392284 921 1778649481731868223403823 922 8418244153786651266867445 923 17356032891572185774732976 924 20724195318302530900014242 925 16078284861279647705496197 926 8605185433589203221032874 927 3285470117306977449832191 928 910668451142535767854054 929 184319557341057829730843 930 27122405505685144864443 931 2858993984439658400089 932 210148443680648582346 933 10318964801723592054 934 316852697368440999 935 5487016936580930 936 45159126243476 937 128376468638 938 59057560 939 84 940 3516875111606393874082103 941 16685314681363904960002588 942 34509286257690779340447912 943 41374362401132311950173595 944 32265145047412505553151618 945 17380590411220668083516422 946 6689791947583450795039872 947 1873107097866564861070900 948 383953468737931258531782 949 57410861236863259666850 950 6176897462523451721746 951 466238891765962091410 952 23710706339334972414 953 763495660016759318 954 14135901842675673 955 128538620817184 956 430918509382 957 279157191 958 2568 959 6954719321827979072466991 960 33074181791204068012174259 961 68618709241443382442691801 962 82599329789987381185323624 963 64740816223532940939112094 964 35096461755790185736146551 965 13615875002916268979099787 966 3850151987999033182905047 967 799013707906053142273017 968 121346505333318970817176 969 13317136799938529277326 970 1031252356706743141667 971 54240193479002279358 972 1827641969251938817 973 36051077869375281 974 359881289514833 975 1403152434314 976 1223774088 977 35025 978 13754889325393505126886887 979 65566913840404729674706276 980 136448836507392161593260546 981 164897415350975519916223932 982 129889850728508810511675369 983 70853360207243060355519663 984 27701481121716022591543935 985 7908915302358449888349748 986 1661175124907694266712657 987 256126410987788484930418 988 28653365347025452463180 989 2274360511647554663728 990 123556998230674090250 991 4347871479873372062 992 91077161196780678 993 992399135247874 994 4446114854833 995 5037953461 996 326615 997 27207473390887478569212079 998 129993139632609021271734333 999 271342318015957216899185062 1000 329187853956257709300717851 1001 260571268473753659967772798 1002 143007718642810220866112696 1003 56336676296613369553837749 1004 16236411192122842398416075 1005 3450470594758336268006620 1006 539883847507703738316464 1007 61532308074440728132124 1008 5002085779640846828781 1009 280334566318871446959 1010 10282904533032484025 1011 228065560389839618 1012 2698456391424254 1013 13746142960851 1014 19660295703 1015 2400182 1016 53823479968930342047363611 1017 257748021533940345188199486 1018 539616610237973480800814876 1019 657153569969943002102500156 1020 522677468141208945616315718 1021 288578419590656399453006824 1022 114529205334431420050608402 1023 33312481143191913731834092 1024 7160745978219867047831477 1025 1136550592856928229155058 1026 131895427238888751587539 1027 10972262379782773604016 1028 633630955551335561880 1029 24185169268233824668 1030 566380209374974762 1031 7242569718569857 1032 41562062895156 1033 73264679364 1034 14921506 1035 106489465744978948424601735 1036 511103258355001043824421535 1037 1073180721596551365872050359 1038 1311847989035251714759313353 1039 1048331349859386871983445437 1040 582206219563473525856919774 1041 232746831544496985892484243 1042 68308855385198378503598900 1043 14848060452550689491731171 1044 2389692141640599411229255 1045 282220964382338107300684 1046 24007485286046943172158 1047 1427012651362624247206 1048 56585703812216635688 1049 1395638847483889085 1050 19205169486795688 1051 123136391358722 1052 262241487232 1053 81814635 1054 36 1055 210713198176236437615684501 1056 1013583592696766485503816267 1057 2134420019616194524502546541 1058 2618750744197843334078340655 1059 2102434322109784598087473349 1060 1174360863349344208677139553 1061 472823712861334192661299366 1062 139993841676097752974054771 1063 30762841810282964525460231 1064 5018580986914206815494064 1065 602856375904035523069593 1066 52402446828099551814123 1067 3202777495055102676343 1068 131737370056118645286 1069 3413931201858263045 1070 50356046797393092 1071 358092516177337 1072 905877209258 1073 406434815 1074 1602 1075 416990329022443882071306031 1076 2010237368593496600505878883 1077 4245277472000461758599351739 1078 5227562473297118813957896097 1079 4216060443134574402647238121 1080 2368323454245926160627245482 1081 960213579604067375687857868 1082 286755084701861893527313939 1083 63685634966442586220072646 1084 10527509348204467758595939 1085 1285682461351606805531985 1086 114118707380538219506205 1087 7164799193972298974867 1088 305258398046565528915 1089 8293482913338501421 1090 130652632676544018 1091 1023713241140990 1092 3031773834805 1093 1863640267 1094 27366 1095 825293359523589782053586451 1096 3987229355894300734822813108 1097 8444057008329323809978490333 1098 10435159854953201198690826859 1099 8453822712943557993173706128 1100 4775271004909563770898009038 1101 1949371008390599142611707301 1102 587072272815262363342466399 1103 131742894718624685682141074 1104 22059461720329582321430806 1105 2737646516425595068268427 1106 247973753379149125317716 1107 15978124556883002245427 1108 704184367831564371873 1109 20016525723574014263 1110 335669876707841379 1111 2880803241684329 1112 9862918181252 1113 7994580439 1114 292566 1115 1633570361118852321516370111 1116 7909162183624371769840450805 1117 16796346548751095858562363538 1118 20830234340775759928534732607 1119 16949726235521105264988776067 1120 9626652813713105357459889821 1121 3956251954307441511905674598 1122 1201317630906340018518808752 1123 272329929248600781981290048 1124 46174971178705898679403833 1125 5820653525701996150630510 1126 537698514096565332068453 1127 35526637599020623263428 1128 1617565277438237792009 1129 48013782657546044285 1130 854480496337866990 1131 7989399802945539 1132 31275112347896 1133 32410849748 1134 2381298 1135 3233802551602631768613564509 1136 15690053811374093885467812589 1137 33411564390206662275380414228 1138 41580023319499340609335393474 1139 33981046849569432759951999927 1140 19403294248942966346511296116 1141 8026767116121865482422531287 1142 2457068193400665053753689665 1143 562544891995849290351286891 1144 96555662889062055412326837 1145 12357832745246830255079633 1146 1163575301553116130905860 1147 78767498888197973071072 1148 3700700146824801946447 1149 114501901561206040432 1150 2156412729597596247 1151 21859378440755226 1152 96896309282758 1153 125156847985 1154 16059489 1155 6402275758728431320863954439 1156 31128084477321855935183646809 1157 66465585397006859038414876082 1158 82998674159028040955562083183 1159 68120299222699768648818811442 1160 39102181643860966887736650239 1161 16280546028282125887035683055 1162 5023154646784590227421747271 1163 1161243470106495759507133279 1164 201708567782770665118496682 1165 26200715763322517332353916 1166 2513094294320217962537290 1167 174164324732592187626215 1168 8434057933298131326329 1169 271557878864354427359 1170 5397902972620587299 1171 59060208820926982 1172 293913783756341 1173 463224884262 1174 94292861 1175 9 1176 12676506002282305273966813559 1177 61760913875287338577199558204 1178 132225320527132494667757295108 1179 165673767285941767603067699303 1180 136547334716290349415045095391 1181 78786941769460673013297073519 1182 33012085718102346699657291629 1183 10264610024575848218852378005 1184 2395542105499466671464670307 1185 420980226940177714889643348 1186 55476249140585588814801457 1187 5417710139640984712712775 1188 384097775669079609393612 1189 19151302329717329991218 1190 640676422972211543586 1191 13408699980261691645 1192 157708515733632407 1193 874402437208286 1194 1651546069253 1195 497039413 1196 663