For problem statement at 1000-1999/1900-1999/1990-1999/1993/problemB.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1990-1999/1993/verifierB.go ends with mismatch at test 4: expected 4 got 5
Input:
85
1
3
2
2 4
3
1 2 3
4
1 2 2 8
5
1000000000 999999999 999999998 999999997 999999996
1826
305846642 977626008 383539493 420226664 682392390 709455819 555684618 610366835 551820663 862951403 798499966 121218998 808163650 164905211 491114067 66548610 759073976 211947897 818354076 772441856 706311052 767947768 564668100 814122539 191294745 830521522 647051110 47117614 304083636 111024486 824525521 967259614 210440548 489663141 976376014 62966853 443362520 97574955 588642807 880621457 244970267 791041671 221248760 338874691 519216729 849623888 318242893 676592657 829953203 634990902 812475994 449759865 273180054 695165358 805350255 968245452 533808516 728515168 91259545 343868481 587408695 441700327 638908305 197665863 176985181 925910879 378849686 231116153 588853355 484039356 231165653 579068808 816591332 804241904 291828516 228647829 871437600 85509876 687770520 892124771 589316610 640365593 295653663 672475849 11427935 218369593 362750851 516868070 570632370 796816423 965926984 211180631 657771160 884957902 957564912 862797542 526397129 304835251 497116413 70712992 958222637 293771827 357164758 866318434 330365913 678283893 17487053 905167813 243395295 316878998 651836268 730298936 354464060 679807650 155310035 135183527 599763732 513843684 168677196 359349571 275972456 611339120 279606458 661567085 755310465 348827512 209267903 317014352 670371413 780958734 651029656 623558871 650061789 414519502 452435423 42993297 390850640 103538816 148913197 381074547 67283655 227870851 688033679 995586959 549217189 373330086 175266058 166403536 876837823 299827634 925334431 688344259 228802806 726444615 805100924 306091319 487969095 128622380 270142403 851330501 883000623 6909749 147090369 940937549 982672489 622460773 499427420 841985391 147234605 351733430 941239793 748204023 137623540 714356176 799924986 887037615 825434102 691051099 711602769 953288989 848211808 394595081 390249848 745383051 547361229 288550850 545870180 668729832 652788393 375347279 987665423 5988390 510793850 514936175 275110049 413287982 748106337 497663198 537650513 675686853 753395067 228915038 789013455 618000765 700897067 485242879 751305738 822917214 882084063 568157564 543922214 371996669 223354688 44495373 534129593 32734850 102713818 399040377 351435753 178581365 692335116 686267833 89945119 173637361 274025272 703546369 686297335 967596265 972380221 273856554 137093288 364109483 19150239 715381822 678949808 545864222 920129184 225400283 883436716 861574428 894042087 86258405 979979765 570663478 872435040 784659930 218779522 710768822 706507763 545790906 40895483 718478002 674691279 865270168 42120851 496483984 877825720 4817558 501486719 924088826 199391220 960386858 918124504 469473543 666170171 102545946 247952369 572494649 266696689 468363309 482609455 847069689 21812175 960259939 900481902 448571819 366947173 715982667 914222430 608024548 934746846 179017836 520090239 287838717 180275648 576642796 243335030 569590401 565013155 72337851 662582973 602580494 292911789 346833273 471379544 447486714 993741618 604448797 785278450 876771011 875975995 181178501 500508358 893415552 466086653 340711449 147108646 768085942 978108726 557766803 109532198 940320231 162469627 533150973 956725287 545187868 644250593 285964250 62770562 592926226 478770986 151688464 990468674 537405043 30566397 400634310 980372523 2985026 992181974 609153945 372242083 131289136 910018986 512840398 958546292 948499663 936834438 53547428 266399780 156746067 56973289 319614701 650919686 432132117 802924293 217680122 12258243 80127500 88986286 641788455 80772458 842363649 545778712 441059129 405853917 70574717 407642588 158296853 246956737 343795436 646794735 41302342 325869387 592564649 916978624 566815838 991318295 685519776 588531378 657531470 786598037 232178159 905166193 194712481 138347534 441110819 720708663 705549023 678092134 309640550 643050464 258949288 89392420 22965905 283094537 632490550 16995615 833965168 914887038 950380064 660476671 726966943 71586133 491564143 912929738 104137542 961550087 797201925 189769209 238920814 704361353 240183704 836155843 590936218 955973650 717741983 204667093 140572807 293637761 788922225 227940882 211897271 405890683 979230242 728076898 625652818 324442945 133824316 73986752 610388453 334483631 853007581 637626481 900662546 219387930 792252292 457294715 984914772 412482831 471950151 787713379 649283135 174653503 72717176 459781455 412410584 622153022 774782586 966664114 103401604 930377115 19661010 183231174 663886792 964160568 90048171 468610650 851156964 989574155 382851695 724381371 107557254 82908482 796633461 324734973 96160087 781279019 910251022 993431181 180189937 82654179 193049939 311240228 797207473 407667369 414390825 798832589 651989362 606634187 450450266 332706570 701270050 475256650 735793823 375518444 384501832 661384106 664067015 209421782 237952727 115054640 719760161 751878094 880071392 601583367 863895272 717938731 961765481 313402803 408895674 151460508 79282445 34101782 948301928 206245114 327160082 831363214 605958690 420930694 961656922 834446094 965183576 236233729 77794072 251882174 967119167 541322285 701764928 557302780 412400511 220218087 75430441 134757220 718082308 820007419 756153908 931156008 510810073 54092707 826855992 825579381 608169800 725486685 569020035 830720653 298877374 936282899 651585305 422898706 800347778 278200758 917106345 224127302 421353719 786952725 88396115 25444057 753765108 702127491 246979959 993013900 883749289 36340184 946912670 184266925 741117527 652184198 732361530 716372751 211757316 215978426 749505305 733014709 938252741 470223603 515665215 734579389 702439263 371984296 815917377 624449647 170853809 383164490 188312606 513017468 119738973 665216816 584105566 848521387 714290289 494682798 814188136 755225252 518923218 304930595 303385812 553884629 659474836 237844961 363636361 808822750 162363250 589393800 721409879 965302409 647011413 194279770 862727601 439675466 19293192 178406750 214102622 476381235 777040876 778322258 11456562 426497578 329366632 600108587 154548243 908257507 384057495 529618735 446482316 438928881 203649285 66187133 460719367 343928695 399015351 371472658 228248266 70846263 520334582 254112121 816163460 67718541 730120303 227826254 132561886 522254219 32489695 993328799 358678951 504094359 482742951 883185638 765516558 435958701 17964075 463294312 494019547 531268188 369513187 389816347 362307279 969920649 538288378 514488064 344459163 69085997 563252776 175219308 74323512 543599310 165165629 358957368 778831324 21266008 96351364 927736590 562262513 21092155 779993422 860898907 700056721 514442616 215069324 895771469 305606414 788454975 162889730 434344634 650802518 507757011 410823146 742697515 275894088 736914407 971472193 795048167 828795564 864123252 428450811 142712454 489793666 988191107 89906565 267022581 388065126 322707124 920741100 117037581 74049916 227260616 711214517 998110646 383921405 242247880 45885669 574626502 98228244 424844374 233699967 555837027 973370412 410511650 146313798 767425607 471122718 535894305 769015208 69961357 572484682 509290794 456238567 971899518 491138508 972997909 688101804 534291791 408992742 661615145 850667215 617331546 137692920 536289748 684533228 502679442 619013594 560998547 185967240 270186622 708179798 622347019 676731372 210707285 6962605 13327878 506052405 356656386 442202508 56294432 320480536 889501633 594427568 254024704 750932886 395889185 505332932 216685641 927494252 428696862 191068128 654183288 606122695 615710932 822304043 4345221 614445314 62309724 805365350 227641317 83782462 762676024 482055341 816432334 967569262 305409116 762580061 610384952 576735887 828825507 363672257 359612115 290524536 457050974 268915239 114632162 877009921 708940054 246253297 4608365 792374722 964150574 217366598 331612223 891513068 626850810 831445494 970535873 455890530 314072420 594991080 913494348 791942484 711741392 573877724 527024063 224241658 384073246 357123382 664356531 415215449 582204405 918996381 966517809 535620913 446452309 610414838 298015721 195958191 172685134 457966101 575429022 689003124 78950389 293603504 248230168 90462298 343125007 489719815 667337793 113506562 166330498 517835025 50276730 19219886 360710743 900428959 679981649 307586007 584828991 668838173 988396760 823617117 405931757 801836997 84485837 504541650 831999669 711794860 644972705 436463489 743222054 778078700 400009667 495367941 82191125 8174484 905426361 674643522 263644433 753819699 809856445 384063152 566852647 62715440 906009427 695959968 724138644 325787014 456395345 192201708 391853099 496561073 413020405 932098910 643931760 392756968 975921454 805337393 946822257 701513082 197412009 316671818 961134092 48723308 96705626 325789687 669362865 800575637 823953877 916445753 466142908 456481682 676022221 927986185 821626026 420019598 891723766 28035133 507993788 935466540 835258924 841078264 381273404 375025560 22548108 963887086 8108182 77308538 388297635 774319574 731199451 910120459 931284994 388584270 48866719 738799234 863212527 351613302 74639582 46393201 757030009 296009768 17878653 387629714 870509969 113451590 170381008 868582475 104392367 731574976 202637011 956601857 183756643 681748004 807489124 952404259 202690754 987092417 963596340 772246247 642023541 383612360 166576845 682471214 146094366 157560101 742039314 764575746 606669962 705568959 584097737 943392676 755793190 578633886 380595414 423780038 619110683 132691876 776320378 587001275 876750431 814786314 62762831 285993906 429408335 252432509 340634684 369859472 536418597 583878396 299451624 580876926 800319062 737345608 595276050 787064348 730824930 730387365 773212605 901798848 539339409 60784116 254031731 889200321 643252248 912651355 202437124 266424474 482083892 454093612 257324621 836360102 183921901 147152194 580039157 819561191 776686139 761818365 958107017 642680530 813815497 217382257 395701530 853183900 490247703 629168472 444964945 744979226 429293738 603350364 263785303 113964742 539307778 296973417 779127807 908840991 570363270 992686839 677542712 263388842 747669253 579352943 424619864 137559336 671242577 147499622 145431755 334766323 684293140 911733989 12822070 684347087 386684622 90846345 31682613 644110584 439303236 315848592 747207178 52558443 231057751 983601584 498147254 353592299 959557380 532715544 298308874 191684352 689590864 979492911 427394806 308525850 773679525 811830451 642078703 944001819 89711126 501477954 380768155 543969886 84915536 365808133 970494668 467419710 480554091 411233117 206815958 254719656 499845216 141845667 181387712 109933817 65930096 229222216 20772722 595007181 309355334 443642920 221619073 670809341 431247361 738053112 94650326 495467962 618511266 352505419 63739914 515984999 32164597 42489466 650473108 84027490 262523148 809972521 751654870 395031864 943850078 225262739 247323710 53493757 52873797 773568698 999297470 232301786 326780080 732098255 763039637 289088489 360101158 364500287 334448256 813832605 786753777 644934678 460404284 362127198 255824366 376468632 985486977 546209924 81438955 143856226 859910186 561452515 804295808 128077347 315003824 288608823 899851272 988391801 688656114 629567820 673172954 956905410 496643496 988888242 189487696 40587247 377059959 494792825 168825175 783388943 27761202 410646983 332965727 811379600 341867520 347250112 337761825 42612505 66772708 964419359 743957987 781705846 507635947 124104659 103541587 66511391 750492642 941043560 864965505 825907595 369637843 727185441 778110880 957079375 375759833 470269912 911578252 204267275 401936147 917248449 169508636 552380471 374030293 787285959 565111733 272578134 130590326 574109668 184850122 112323025 752594267 327823705 59032731 158015051 655772229 354882901 869849794 516174246 688831064 714960908 516239051 98650024 247318697 342371952 323601868 259203340 102329088 750108600 296476016 494999155 598757379 243754847 11761828 131848828 849246682 457143995 326756021 412423142 505800313 728816839 167766273 459622268 395802987 361129868 715031926 152124472 616368204 419574122 444240189 430444085 749607672 480313062 857296445 754408733 956555584 251789335 904606402 77596881 563453872 710194135 677247619 77297758 242480919 191008019 81313165 483924620 12717465 863791797 962273645 118996157 602525823 48013581 909703111 54396974 392605732 168958981 774334087 607285284 555734739 672225560 308710095 279920736 987271769 506033182 96633961 916935298 966450631 395201660 56488532 142540958 818573602 409702640 367611212 544943059 895742581 673453640 292774137 217460979 68833480 907251004 46100286 220488907 984721588 28001947 212198883 24469349 719784416 494871485 318708951 305725729 142486802 785696490 884900097 588848190 915590978 371394980 455131530 392075891 229744001 93411693 920655893 720932075 900298148 838971868 440722684 814578255 106549311 698373135 116998706 877969324 684138693 608019010 381559716 301601176 338822927 927760516 247430313 909250953 602301244 860999245 860842350 964149709 185732933 52110694 507568976 42875673 723811797 309379884 104555183 210199556 791410675 112591605 41704686 976218457 193827422 200954415 528061650 923475833 711656571 978123381 643029955 373307240 784900238 772015739 211929514 330280787 119647865 759972225 718452758 568321796 612398462 127978652 150465743 680344567 884319290 596620923 455187999 398890558 774287511 498108955 407498472 853346232 933978882 891524350 558689914 50422203 265369073 686648365 161807561 875619733 944331602 174820746 333381091 804521138 527891263 592324345 294388298 167463758 19418615 379724830 817080471 393954212 582212326 597792 981380288 631634763 972692827 15409120 859226044 16497641 18550268 7735091 707322721 3095960 401297989 130005270 174774473 476411181 368217934 549115726 251560094 9099195 69827709 431735948 435981226 22277845 754407364 711745412 253399199 339696392 412300898 907645614 619472600 185732712 74685875 508435355 886189091 672547489 579727293 179494288 111248593 197479878 134285612 18746232 488233247 530054288 710847844 961966508 561361735 446406197 870591365 52822716 497210643 916509894 375863646 402547474 50893189 770176770 699416523 256444740 46830200 972444046 844965323 403606208 819071771 841963933 210710280 515536544 815893393 285201155 564792932 703800378 104104404 694198815 679222937 994052854 110618740 231942555 696702305 188593771 572882843 359079408 148164304 386787387 154396935 665650119 465252177 404064558 653237129 280119886 312532642 825408773 700722890 444669706 99929102 430760804 503737773 543524138 465967322 314401514 39990446 498191715 97442511 477435053 422170342 763585532 8998768 6246321 147545200 912831145 633849475 261054401 924228923 998497142 886233776 686615374 852326233 827388136 633252566 456813537 502608517 769102668 730484794 211957075 134645045 933534726 233520401 165370594 139832476 538600564 104619123 35713925 418422006 886628596 520413999 536045981 171522038 643489807 793502961 881336433 226564619 691627327 620043720 413766892 88893616 829192734 90318750 505228227 59218979 626977212 574583547 623277996 851779582 755294279 302688132 120600441 284579397 60040928 681826211 846480605 831083018 842879920 657307650 14647227 367782884 114099277 658500364 564344244 59998525 374749504 978256696 589174601 22893768 587874877 247133763 802413454 883235450 312707851 75105723 373166206 350470541 825401266 379918922 87259968 392066872 783286000 783787871 525256093 676724051 365117669 718602899 827480339 731891980 507380277 113639478 964860739 960951685 888078863 401354508 572768726 704740788 789552499 68546890 250150940 712947263 191775528 535720738 64871142 687726173 724478641 514986820 464153584 816582850 681731947 856040098 769584022 435496457 359695755 771011200 799379546 481114000 467439412 504058042 639901947 269551186 894929797 499388703 606296774 925503760 716024322 627025757 598325685 533603052 355208084 38889894 355080198 40642671 542575715 861290264 340817840 259736282 699189224 775015806 401766898 8445354 856073814 501204256 163104384 667308974 161264281 413628893 927014288 287077874 562778275 66527887 63118855 652407485 420216359 324764453 155385316 90633065 689359608 438982452 297892185 749282303 748516536 527279892 540151095 736719284 581280323 294049560 659572303 153855199 258744016 94224821 362059262 773932715 1955580 655595490 331178289 587020102 465794655 813035762 245557649 37546534 159504012 835215434 470803697 288103477 270214778 939828451 543994575 445696849 11312483 928040505 773555740 663680910 801153883 892181485 966672209 190951491 399365063 992616121 952030320 34732224 493583221 628936431 370642270 963999988 855188996 898254117 170461960 156296012 887738353 513616511 327049495 76779162 775977180 191123780 115753986 356941137 173902232 548669006 596903977 247970484 598897229 863023989 636928828 559500491 257216188 323419285 921998340 573810075 43952416 120033347 910644667 401691912 214937012 203723098 750871273 299872317 972888123 528169216 756778716 346631277 871446643 823312739 418204747 123093653 469566944 157946244 134365004 500603512 694243507 784671426 951568697 102401065 900127861 646943688 474903996 796200634 403387843 574110501 131340806 278135526 339457165 671215949 225893778 676823190 178837199 945266506 697146776 508098461 711219368 988135466 179179683 310450084 297962054 580712477 233295068 33369774 575892352 488972462 12405265 422939643 363822462 138043013 380840431 489253547 816890014 397489362 446658013 770279416 621295812 115562587 805264789 865701612 75811300 148771321 946799741 826190033 594693929 624646302 996959006 964850495 307538318 988107080 588356246 579224370 92162552 271353703 52050819 733132217 870208113 764892458 917337373 288751295 803036189 935388704 737882977 414430404 783753108 824293411 335747982 641642002 302479444 418273875 912086212 304183025 108140082 617203450 2231607 915233673 135385668 257383867 70523350 548877902 861594054 851868508 339020738 308529783 833966188 956644786 204905789 77152433 924114300 648827278 326347259 508841137 956008995 706652465 341925221 982471366 334495558 964289470 923604579 5721399 193695409 260609008 295488093 110971428 760731432 561716580 542988766 94429811 488622933 388883618 454764290 14282178 912070823
1298
97112203 212375742 567486875 852508979 419228118 379101565 896133933 722162299 362962878 668102041 220320778 841295921 445268642 366226443 383118928 609878020 704874995 84492538 472206790 916859218 891735242 648661680 526793107 95366332 242637009 413853809 555292673 649197210 770212658 310891409 214719853 23946734 635381473 977930342 599361825 831641334 647163201 605653947 790339684 372498738 756962667 630415915 267976920 132337750 518094417 485326225 498846599 418365218 873738471 460938874 579156268 22826199 913458334 374135874 580593433 724018169 484135985 378391880 854197046 933028372 194770862 466870393 783574141 300470447 737485844 146139222 549871404 842178571 492734532 558394570 462019297 968912652 695601949 726323684 288035277 856903114 61734686 45925930 312720456 825488470 529289967 689029439 524332582 203886201 926963309 332437935 627056569 787971518 537321158 538106027 983418603 87430177 715334587 260890911 752674286 156893803 721634992 152258673 92188281 487719576 60137773 134304253 217192580 565220162 112880038 551764966 998201965 377975753 773671702 339435170 108616216 508776282 332518479 991826048 570030942 475688364 556014573 932922512 8615628 926682423 309638649 712173215 733050089 158168 795027780 273833503 423976990 757635733 495860228 399331035 702820946 501577584 121711188 331844882 372914678 828529118 803417658 292318296 484971705 463492057 829173818 60821775 773826544 519308351 456210559 923837496 653999171 742004639 722109137 996070548 228756064 60690337 201711246 743976976 333058859 408701042 244258026 998251453 713263047 373676716 813498598 716146737 865913632 798088000 737170152 446802876 593076866 706604079 276479528 895561751 371293988 599872287 901348921 635251784 195678610 980375219 263726890 44568527 741461419 466539849 203380650 331943514 874813814 937178943 927362088 809851301 518089737 752208024 940552533 19117050 635686690 589837377 366452332 773122662 768341904 115600524 14779883 766186348 725559714 210075398 353984861 423429172 951006780 931298308 589640908 822113809 902696403 226708367 269287368 798319987 612230947 740453817 593908999 74016987 504840124 536852693 706120449 43699496 469340942 205168394 334928980 17239102 331369566 847130347 791101662 992358711 475844146 963781028 297044651 37389610 278006117 680363174 517355430 827816735 702668205 440505250 568489839 526615044 544912071 748262449 819434042 687430484 284014159 765837235 207223424 737948639 634055752 18783114 946209393 96433563 691571749 575364731 137536646 74323106 446413386 920189903 780711573 77310877 719672558 787011002 493200841 407150648 286506543 422961403 51093825 282986874 320678761 806617672 482769042 264807825 588110445 397200389 399828864 142541776 94722135 326579297 906712028 182626299 634703880 197139809 674316374 80548766 325921261 29494307 755838713 91569819 416738915 645109370 577611798 346249162 44210544 945267464 314219806 419968414 37238369 370644212 845285012 494328848 677101753 483236359 413980996 37933866 230128270 43235075 540486238 600313597 432574618 106236359 666404688 66409152 556555924 994150408 947984392 747670729 767909859 94060238 638557520 819422589 589624720 992123235 499392342 68316071 894416411 264142622 603103118 324649369 821638329 64627550 100624580 253522479 353363127 368064185 243096583 29847278 253745588 76038157 831418359 181246559 340883288 335646734 141692126 700425541 205415001 997199236 501059070 494865227 400485136 315452560 75938042 784753846 650175111 572475032 416952734 643104891 150770837 823663861 656175032 863112346 3183607 502027604 600000620 979008640 153467945 732102616 594382397 542412890 802825842 844607134 145681247 681291310 569913184 770590186 559371578 10571207 434794264 640816938 530104118 177967870 398602202 245715816 832574313 433337515 111708775 80955782 783963704 669545813 495165748 567408036 195673717 153471535 454601210 319614919 229669542 430164265 20125308 460186837 618959016 323855022 490942782 417420716 529303482 706004627 429814485 894324664 95692763 231152296 210523609 484231680 699191722 588266888 321037187 626744985 756903179 489430702 22956087 574044178 892332216 199273358 186590480 694773359 191974094 422144420 913408355 455062241 241828406 547229624 374386978 327675347 990660434 755285130 106323276 382067131 478663902 100807976 623486171 291944324 584066218 73961442 852720578 651325083 633164039 936294483 875301677 262635829 29579645 69843499 988806554 284080883 3640110 577207710 723259321 881987193 413130036 52980061 757372704 850056024 82347586 61950185 929098073 493329757 756047908 448124566 596102845 161894075 101068630 695306880 434560817 253196669 376139238 847302776 943952841 290979814 368298754 523523158 506211563 343774830 122586341 7440475 982918075 856684576 305550927 966451016 287395323 724664130 303158942 138651241 943379321 360449345 158723213 496817491 675386365 344228164 426968834 500393366 296596695 536905842 268456687 583204081 514761742 578572071 222411997 568040848 110945665 70079448 148484382 277220317 298089195 754945456 991660479 735164680 575742443 716100277 645654991 491741280 664433017 423280461 170010603 742898630 928148545 725440847 313641771 963180037 208602447 208806345 110800696 590909124 882011274 442858404 164950414 375464519 130443795 352106002 397102647 308106282 339088739 388676899 982846157 767031306 135082398 192752466 106646740 818830843 257182342 321625359 600410956 290604537 601118365 486777041 238652116 780255181 239088157 606980323 146765142 851006410 688024257 937710760 182571781 594207786 27228779 599650445 489648205 999486937 718751202 432118693 995250527 453270846 446856796 740113985 16037707 768931665 561637283 653009722 19415198 999527775 842710522 360719819 34901819 110243112 64960364 193204615 366101064 113159206 499777901 65497489 758647219 536834339 870000149 145257720 854541158 894857292 338462914 272484286 667599397 966566659 386711032 830443769 646538142 356411978 724372274 840796473 975129577 952937246 179022912 47648337 773622858 866277725 9768936 259654129 55407298 385644213 911081811 283108586 194274630 361958945 421548825 228282426 410681259 176294144 498077302 968518270 721407491 568625302 629817231 276626581 703618558 754142440 477441600 70884757 941287384 120106314 176623443 948473606 177825197 991732085 573728071 49868433 332082005 645623174 74005784 186123787 276827502 257408402 51913817 767321666 145103389 475278497 918698981 424173572 396974241 664073038 398438677 656292957 57908586 66624639 415263819 541939581 369761014 462175603 209100025 983826582 367417412 205866671 696959348 740525561 265741820 114464561 817040951 476251306 240148666 751038323 37308797 925265464 818162148 761579590 771071467 416194808 750604688 879748103 366213026 897706289 318865149 163816054 390682758 405346324 410446625 566570188 606023302 584224385 736266360 347794945 129213919 261477167 981540619 335625517 430638974 764213412 151290833 254204732 214237584 965126353 807057767 722042357 208231025 331736793 711161011 473951810 826806605 378100735 66099614 773893520 982714637 715949356 523619063 67955245 977177079 984803972 361331255 797814090 905871050 434127488 956524274 678818842 103964474 941918636 73495844 670097452 512615930 768483402 970326034 902895261 251582221 903002226 967530293 80494915 757939565 867799937 234103341 212432265 498837551 207106211 257534224 31338111 90795261 400125165 758912347 227723531 86291989 316784281 78307987 119486118 371640955 94045398 503519342 599148706 659916824 514936714 902859331 870545980 858956713 501351028 153818509 926175674 852156203 915170451 615439796 354578768 612167863 417528790 683361299 804665565 582929139 614016375 673349745 949260162 94888209 37334474 956028261 947698527 701803106 174143291 821446943 454787392 643035261 991851158 356327841 720046464 682492855 558132967 668596611 922944119 968391845 147088304 599631476 133290482 807959966 281451451 41961598 345923228 807141955 159386576 784000228 207759123 907227275 966199183 390953246 972038415 556064346 389795204 184672777 661284531 588466923 508431318 798212681 815184765 976206794 423131609 590807491 373696254 317236919 660303888 796749279 676703679 638948160 225198632 806426199 345244967 249861170 499742713 310379574 5611008 476191488 686779824 919776877 982546943 330305313 470151160 8363959 936663203 239979855 33636807 654085671 521089213 759704518 717255557 640883032 319776149 8881381 676032449 251128520 332727339 836074573 919215748 222192512 824132282 625260134 119872020 763004621 807552751 573873935 475375712 422882581 134242374 128393597 688603477 671119360 249042633 904785183 494779774 357340698 81351270 728205571 11753345 516008912 174237440 736053589 578604228 195552084 112690833 748292847 277942343 818555486 561713595 66682903 815180962 620412547 530035458 22464783 491124426 642044141 796801196 448740978 101242643 398655152 341455051 210549333 305436295 365683925 718375079 948546259 530435511 473012398 348007748 579685235 849692596 306162435 199600711 767050180 620678820 391655168 870820083 809557181 609585160 151795494 443355453 843136869 347134458 165516944 682694553 757569452 967811787 152431519 748840050 854893036 860912212 105582279 637309416 904274103 971630093 346198557 217970216 958607698 405946881 576871589 364410624 431513950 888778332 934406240 451133717 253770317 840140588 51263562 783991171 276112966 829940201 568840672 781132460 240922694 342432949 618020674 857687681 778321074 662301922 718698869 449878448 367709118 419727562 668030887 437900567 761901058 583802671 934138647 298281973 554472108 557042396 43830587 512018118 593107147 82140042 350286082 724018095 933013086 592483551 242619081 544791162 999856028 730709459 698821815 562926545 545569890 513331970 140857522 144575737 517615745 143778875 325039681 17506927 210580818 209358699 627724539 132326543 47991636 224763775 820233747 457677179 353609942 685770112 358342200 654824282 286386889 984191382 700150927 301684973 791528919 968109364 563988378 890104651 994787794 634276784 123625043 573362841 587955259 796514059 518576823 332583393 642206770 738790717 740943906 766997415 206798569 784968058 462045259 617742827 550303734 416528953 393782287 910858547 664467831 560713473 62635572 835243820 50328791 642711440 471895291 61741281 176354116 401622234 938183822 724016713 745767206 367890667 715055756 805079196 565573442 962875535 377797539 81011397 934842861 434483627 176811958 288965775 799127558 224830772 402410942 504646441 156475797 834772941 980744743 634727957 260136993 115312230 927859087 240495101 991784778 904556946 763244848 883696527 156507771 619376983 868292128 963669146 105943462 721220803 198269299 217873084 52401598 88562683 365365908 174875021 889631648 82223012 515255570 845276151 280407610 319252779 931750576 537310286 895586169 883093925 425972419 64832939 913009563 173314372 164644073 592085856 430739453 814708305 417825917 98793257 105932455 476245540 86807455 143963778 144211440 635195540 922475715 442426032 10216284 372143056 512797049 277766998 25289998 1656737 440324284 812962092 276926771 281007516 831916359 376627733 461346472 284130765 351509321 522008552 551040155 846988903 446956772 296388389 363775790 627508285 300573068 606877122 318718213 211589790 881622498 162446482 783468417 837970684 561241369 909393425 28417132 655314366 640278570 87425146 684329041 909960401 948518879 19256484 280695867 618925685 878289390 80549482 450694015 827742301 113057568 56837993 73546896 50551259 292095409 734718779 410129004 813304893 952700577 556012688 343938806 313991644 219301097 676273680 988580092 657233497 925418352 162149530 852905804 606788586 220924242 920855118 521167615 250920373 346706149 742857657 69368332 134977388 186381057 550765260 167471714 440588 844275858 186488485 934130373 994227855 343713491 17921265 490541150 205276157 731211916 911025345 992550946 69296971 960614614 224586572 770350939 746665868 625380896 814650764 392301382 950102679 355827206 852326857 848425708 995526371 707286850 419622934 39565579 124292425 143309383 209115899 38590981 980776912 450728036 696720649 63281417 527558097 101739172 431159109 624079622 720047095 38710050 142113110 428826484 228271462 448485752 682794908 137833074 118114200 845174020 368379117 785718556 371060575 891895845 181884533 442881208 961941022 939135622 788578394 626775626 959963386 359988994 351055920 945697924 543628923 984049801 349439318 596809051 943632788 768788824 221394470 590668651 163897652 568415767 288933639 501996270 920742837 229586531 545528996 78246520 277943119 398490195 274915876 827567572 802192842 761640411 178150941 54625750 850437795 70527510 304621268 93465576 886121526 15585144 528144872 244152698 533018370 984994660 917401350 831330144 494161262 398033796 244901311 860449662 593631221 336972631 599235714 150714132 165705755 475118077 460797625 483228413 345016467 687351371 969319271
701
666860536 819232906 321092019 930405827 310808806 838950961 655159149 668586967 389244223 787803325 770670369 284453335 659945166 535984551 247271058 829215505 380869908 246156655 487860524 54120570 244643368 171319439 945594947 977741925 660027113 71042041 380725304 478605859 8802793 640168253 68815278 76829797 406268978 242381191 144057933 27031224 898376242 357587796 436801780 262804941 963768908 693002337 902181917 398283303 210660031 844846331 977982133 463306892 713224442 875117478 98745392 169645362 266049151 885526845 310259917 262193427 307637449 825978918 158738395 497456773 123921238 665324403 558139658 890867559 589514335 609847760 505433537 173273366 559218448 6515124 223729577 661315043 599710860 449478672 142631509 36670398 99723050 222869605 201182499 673925969 536182098 183293082 139507078 355420220 731567239 114657889 272595182 786907399 70832128 674269321 924114040 831538452 8339069 558326176 653910993 8667048 496913235 906486336 11770946 528159845 965693939 645889578 55995686 13036881 547441380 682253630 931065822 349561797 603363379 627289643 667468944 945607757 543190221 861379108 767143239 577927206 833251414 767806816 932978440 419010384 764763866 481249378 659657560 529182496 2582569 138516845 898466192 812712373 135009982 897806723 925154150 512974907 33178873 548816305 196254051 655409988 231830321 35309625 413977017 318410965 681160830 502154970 524812411 572481429 50758182 302655637 154108163 999213162 582797795 922317718 213473348 603231983 806085356 861670611 582097183 406780892 135979874 628311928 844999118 152902749 769130650 309211257 41618929 251360009 457069849 103498361 708704174 189497773 917836182 725059229 12766722 489976350 861684462 10178509 569026492 306305661 798735784 276405884 912974012 833720532 301339883 50725640 481566137 443383530 848267231 751698270 433138329 524143267 144138972 155866370 800808753 455259824 336190904 44125721 387074957 785850185 231972787 849994476 819193948 199671662 786087466 285334178 585383324 218426619 936860582 715466543 229728226 284923607 770972393 800573035 850579367 636289728 820052385 170585127 227176174 440010618 250872319 857774310 135645081 161665530 572019479 16066022 935934201 993614745 129962372 22418312 33884325 157339978 722656636 140854713 684944919 888423938 184403498 570057252 85187267 287983285 897552839 430618159 999541391 181616225 218179357 183563234 837384861 721303712 836250302 322808191 996543227 3086512 896415214 669610918 422404871 858348436 828208893 855832445 810639410 531672837 992280877 938533344 971277503 703150784 893350742 61994322 97996856 970223446 43325185 231916406 217577641 798823934 789545496 845649488 65269083 735307816 835699598 871347208 621678937 85906305 658997300 29755714 997182682 341386185 282375023 807605995 670290055 173266392 449179760 929025991 489076482 368635421 907891529 705847084 373722071 26179840 480753090 106232161 785751973 460918875 747691473 473209925 935202183 935118832 742094909 276739711 140257845 842582215 483810403 174110283 630084094 22693204 742316564 816333943 86796772 639151055 678226772 23997962 786659717 794399311 972400924 784049220 408926066 728376017 817790839 287000152 430223415 777359465 296807390 215035280 3245044 441677599 861711947 430999266 151943297 919505961 148531200 827313555 452375719 78327034 378538644 360644553 269101426 892142405 829031990 920101135 373704976 733201197 637116784 898298696 579136246 274258257 857047097 808567454 854030711 965142356 840262613 550347166 443027549 417863907 209554592 414394736 368889294 800604014 832113017 941109827 144634912 434367895 995753122 784561022 873739271 261740332 993818734 562974162 908975306 116444917 582133274 971608528 12798852 510659900 263779592 99563508 923096720 779327238 953299191 846140965 483688691 473180822 936417504 63746680 264453710 875323489 602541729 243788244 203169382 53195124 371801313 871954552 347146570 666431427 781616448 152302581 42191269 93552283 425063138 337370832 968531837 645139027 272584218 968022260 656729060 352829836 793181319 709072148 653350714 169872813 951579330 199878888 476326333 384194227 327629859 850902015 28269595 840509023 603033917 771038806 83725405 619577751 598401069 385970915 539051239 726278904 786421108 709868923 394664446 648074133 87552239 119657210 836847323 261448118 211073032 686292796 997044776 489234304 376790611 574180222 828943790 439627628 390831870 129932614 855218517 366950174 36375532 369959208 367143375 639044405 45553446 372030048 198297343 934873824 562210750 573441716 155361224 114029894 434307634 399831425 665119682 92398449 40307139 664597189 21223258 456956530 761025977 976316294 816837212 966168700 291761406 761107401 761734176 841657467 837249222 294557598 73449903 281632403 718482371 349970612 723535900 721717202 330848610 881124146 633338668 612745364 242238809 328711947 291505476 476137365 901663320 256889406 325676343 118727696 802091526 137252406 5603099 121200711 594105585 929738824 644602423 353362021 81925362 572621090 148295892 151230004 625096784 935924559 715263088 158448462 804760615 151038690 174849775 501365060 289496016 447436173 573605713 766372586 639592540 264719655 822585056 132016398 785993407 87757572 144058118 766392325 294855614 133353164 913946117 1806679 228799196 765990229 313706494 791396125 27849974 248528286 985329169 730649856 974911322 266731968 187817637 797127486 612788119 293426251 690841743 291123420 857509983 974914352 504265957 30653284 173884888 492051423 84664103 712884013 751857788 350243190 623486257 40115033 171161773 968300794 689553740 414065821 725511710 236638585 869718951 206447098 330618368 185902272 692584929 28420292 434718988 595587645 921387583 116876920 65061896 663609674 876032472 784667914 269155849 247888411 612997038 807306894 307558681 139345451 749764238 808558313 898355596 833101023 409449245 239857789 812806 337916704 821488553 235300967 162482325 517762909 612748772 388009378 108402844 868454377 254198041 624852714 399549400 719840624 91062267 613523549 140390231 248362392 672861484 287772286 675721492 930858408 253841579 744627812 110462901 92198471 552234541 420478726 491275507 686895399 426816060 527100927 325517185 561122863 622646611 868609789 437052958 502214171 106078632 440642281 553010050 295619636 626320200 362367571 139132637 465636209 745250658 128984050 779970342 238978815 45218553 579737885 599230006 986612441 619741752 305855177 852448575 679088253 818821661 925090734 285918558 895697008 474959181 506322427 622013804 727024947 184888904 171040126 291587248 765067833 518903946 717314193 486349312 983461061 678404482 987557606 954919501 587772458 796509772 571459816 701888130 222693508 201482364 769493170 239900918 383895861 292982195 958061622 343559122 120186838 369526482 923846941 650656701 226069084 502076048 248974452 108879754 463963298 362536035 522413176 925606916 770434273 336870130 671457949 426141494 396425983 26145833 259229097 717536362
177
891955786 573352614 554607816 96311627 674685684 352405506 786603337 495759434 368834571 569778228 664450898 295978244 981928607 228378322 668619066 362112659 174126007 78603532 730047650 138043903 858456141 70045060 601347607 864605761 470438350 607601756 86216625 624125104 432683184 360149120 145078743 28022862 982100746 10046382 398829031 298982248 543578691 379437587 773071613 344388507 197563202 929890965 551866025 326234792 281391377 888048817 142759021 774525815 901881761 226697290 973864545 139212206 313898148 422615565 967489839 203418017 263700601 73775089 574328049 596348137 23187234 940415623 890316318 731093286 426935975 669532867 248009207 424185079 402662313 312161276 287821133 49761229 572027015 798048234 279703198 780574207 719391445 149419185 702396669 910587222 933477600 74930292 895952600 188641158 677796801 185189952 971184922 415594774 715851612 146852541 372221134 219701089 954924972 900771403 190979089 143181163 891642559 45610060 687829190 720554496 747704952 328301725 407472294 921505217 941519178 849756152 235011283 642418762 209127057 898463468 999370666 676649590 352709502 410854759 652196404 768311422 861999828 154412222 741569408 438452022 90414613 532715843 572384306 891242352 792191300 160202105 296978302 881187315 674856405 426729761 313157494 200821206 495522843 31422240 761024388 703647558 746980969 409869247 862856737 259148278 581243973 135704180 998039050 491778607 261083710 464178437 299305251 756644798 16294372 574301461 627920111 998548229 505781561 505592597 551981142 511943751 888081704 721572316 608063666 75407470 676724996 804977554 820303973 103529385 366488511 918738095 740546994 147067456 89329021 406822073 626208523 322454352 18768333 856260308 437637176 261822680 515525451
233
138779742 367521049 727718665 110949471 840010202 578359403 256196017 659174961 103692185 142377680 907313808 459478957 412499668 931913639 158484775 193749753 407051440 51605725 850796748 666499730 121550001 423747010 647853650 845191869 659623534 481414557 112075964 257137475 53666402 853799556 766707693 993456358 877587189 109245956 457846798 12858094 904213218 193015653 208963251 608039867 272401827 590135951 559252245 846523042 657061403 49751837 554054192 645636192 139317281 373552136 105050779 236631754 804176108 747971821 515971905 589245335 134419344 445071770 348537959 884492826 95806888 315835225 221070492 261811958 96131446 125803985 735204629 690595204 124265824 628687562 503017340 773222095 777825652 116273451 441015380 279078720 443458197 193633462 134021953 791422269 39716165 589311716 646414061 907149060 485499086 793633623 107029177 892439185 126267972 325348125 567458846 819823677 787675679 235914716 307916715 662551822 269923947 101316339 650584560 951458754 311020123 900402773 926725647 79675373 203721990 296390876 617172845 626423931 220588012 549097620 105963965 626618384 273662097 431940745 317220411 794520310 43855435 762939057 865043940 130952505 229799472 519549632 348706037 730825551 666324918 217212766 14126346 994430722 533364674 311507449 189965399 570561392 902745006 55901477 472397846 968378185 221484576 727805798 452527067 157051354 582297198 636079112 106374750 858492713 802493738 977280958 380219581 90068367 89140556 910605335 107521115 40729175 609406853 536228656 994158075 671694622 547728128 916587758 585718174 483198756 751246704 466822354 542183644 328670846 991647025 290085165 330217503 105861632 853039757 420186688 372207388 265481729 619318527 645822231 155015817 866021885 839282192 549796478 465554130 265591745 908397869 296378089 125517669 424673937 706245831 251769501 980388830 424508107 110653155 680395945 830322637 346779317 219975844 926759883 519276794 148535483 329261997 95450820 580464390 980152016 145990019 510131289 431783839 277438111 68867151 519697074 615130328 570787878 733714014 460529460 334174369 261985311 633709872 932446753 512971198 723575741 506769213 286998252 829772259 121033349 728688906 319206281 527815678 651996074 971562959 369432917 309720622 117659556 771559883 708574563 933036507 388762232 578382381
1173
825262159 646534306 546496332 28748408 389609009 409351694 23063514 579531994 537650284 914684000 561364140 656961767 561133276 814840730 643460658 495927473 528901450 349386700 290242971 950244439 857557878 59798647 288908632 697111936 176011367 808742210 241969077 132228488 296359226 225364385 390266090 372827197 119302202 720058348 71259090 908249013 157923387 737223099 326905071 90654536 519828887 311983057 245235562 735670969 860190545 29902794 500085342 365540318 922120779 739076083 470825423 277136588 829086580 548909065 535291013 153248324 5091961 865877136 233087855 143593338 136277710 55776586 553407491 665610175 729201150 254205567 160214738 498769015 518391080 630592787 912963886 531866839 763732681 161611035 457855124 571472301 947285940 307132942 883835473 536449168 721361626 516690128 888132158 458499017 14460890 874337265 8747764 869516481 610187963 135504034 12200909 823044205 696011336 40245386 265691160 915716300 499488639 986470527 470510522 858537825 366918802 932332619 655362420 960458267 299956050 729042980 471980484 35928567 362753381 738498972 405259864 754818662 25230908 1417485 105901360 608594773 458020413 391747564 324378941 481130129 302368881 405204353 65884046 857073762 513570206 359675594 321183409 58106545 475490447 402981677 924318798 658009828 187860163 149112709 292829886 724335163 181523590 493488539 752212647 297672899 190299218 643354260 410552329 792593771 315033530 328613971 610509292 568709473 643063869 573890081 366925486 450051963 652810787 951131769 205857340 770825647 6987309 636938696 901697883 608597902 758687433 451253214 186124647 770776824 747450755 247201149 38149296 448022034 388816735 800259349 45836281 355331934 689979680 974866828 541336317 318108027 312318248 104385140 719168935 539105254 751644975 963707033 843385432 112688805 795912849 243664568 728547622 746945507 153640561 51156889 689762055 50776201 352214959 251054833 590439563 390981706 146803330 847123672 78142994 883813962 420554406 794303893 375624372 542464028 219578314 826544106 7400365 658507952 80677575 422691449 912793602 743945115 565259243 21840938 640894166 409079151 413178561 850491076 366804572 179920904 483593553 964381979 796332492 419703824 7377044 261440150 912216899 37082366 472188203 653473532 99733583 996800031 887574245 527184571 168650178 779004283 122720671 353216063 91635808 914741045 600217122 831162919 550393059 109316728 326087333 184813249 85250805 568039523 340531861 878504559 624620291 84706923 477939474 887518646 389537301 877041263 90530082 862187620 971988035 467037134 264288431 210443652 526398243 503798922 636248340 421190478 380657583 335476634 282458536 951040999 857314040 325506020 745592964 659601244 575605339 192686074 555939936 573648402 614825044 603996939 832283477 464412922 601805386 567792634 452596188 586053349 524414861 655533067 310022107 589530521 996754679 324368982 181724396 109246491 381834690 348938591 588434059 737624312 428947579 782918148 187195528 47234763 893846380 726664277 326457154 308495324 820318334 941255264 728596911 656936876 614550320 172943661 900761732 466177042 517974887 7960290 889931212 539172408 854321190 782501014 838469952 599248211 252957547 973380575 685958886 674653991 464070490 647398639 413888180 144328174 118153074 916061571 181511789 22687630 67417672 23202036 16793957 955579127 183146986 766513048 18504720 960536880 894257531 358907826 64627022 444472504 557093524 782709382 178296392 802636260 208726090 468602512 73173232 863106661 676586126 38089001 905630703 298917012 553910342 150353548 66060279 516665742 550182196 883631185 180169522 811946635 454956190 472454590 823230302 508472335 652887486 585744081 426234188 294738299 132182907 150953498 292807054 99771515 322279507 446700831 641367844 608827988 277330478 809323764 973283139 559484857 67788107 46016017 925503847 186465815 534818152 501780469 148127462 654782256 692421579 283823332 769629351 889588012 864684021 836697330 560428385 158347755 342284479 94638855 450062181 108841085 800620931 596484224 646653420 587382225 936551909 757071370 826316678 55367469 909752970 308073242 378212325 490133074 521267390 604234454 356856403 255734707 469221679 23139182 31105170 837727193 606414964 797048309 532906260 517521985 82009427 657088643 645069219 230779711 164731790 395647777 13122194 907209115 839768284 859119977 593591561 877898011 383440032 423222873 781601751 871056228 468267599 604565908 237928779 680168004 11147472 268108392 306891706 849284594 476455882 119218090 344002556 616464955 669273255 524621732 983595459 589697562 147103416 39568677 133700514 567803691 573742425 945478824 730034721 319684486 520699676 743736602 976211425 568665912 451697788 811056406 320543466 967431952 776481153 847158323 247932006 788329070 939010556 48173528 280920780 988447056 177659410 857402073 982595191 199190970 118247234 725423451 357117537 534059572 98555705 986178735 268931295 801115271 728400162 650367378 350842549 328953743 255768101 27399000 750137959 328960744 790952753 729708974 720423828 814045408 987694418 770926027 692510256 171283704 687012978 43564666 729720445 674933725 833060918 731699159 369632669 168145002 428448554 313688639 365400122 297585728 814460115 495369817 274731571 926400088 16469395 907822770 729326707 489742209 318509701 396859674 143884727 959365401 873051600 206703471 776566415 891227364 908736802 377086708 976365055 130673485 872584244 478679407 544071664 466598146 212510294 298715227 214500438 645482017 575957760 531788938 719108538 373198583 725469837 337243731 62443694 350606957 751660424 88985222 603605498 485856296 462125871 822801020 385908222 887616233 383222640 733148884 581986667 543200518 776141365 396033115 963562623 161182425 675926357 75146741 189534958 129073013 266549555 343517459 259497386 141405119 300813990 595262329 931451049 871618373 113502514 681590561 510052057 709683935 538333606 272519936 992009445 924817567 474375297 425135924 922633842 557346512 138810340 394228695 679551513 745739100 754776163 264532077 211877138 43853677 910722663 17310500 786998196 293946885 202337988 572442328 103589687 401757712 761887023 66152201 615170927 971223604 194137734 427103604 135996625 498707967 958101026 910987331 114392551 312564532 283941921 557626638 746268160 246503122 948500786 345179813 813779646 383201741 342489618 300133367 526287123 60476907 652357463 195213578 256850984 283631496 666983165 515465783 979834667 809874736 7795524 780400321 188702320 399415264 481374629 53338656 461557656 382394799 620885171 69299352 953093333 178043556 971150255 623310792 299305289 609727384 720998646 84092893 614026554 911170455 413974602 986807098 431523370 979287802 848498370 316902648 580113648 950351807 325508062 436309522 903611239 463488725 659884451 898992818 729713930 403192835 715195187 973076018 633761388 906173957 200982357 908838175 583455139 775115151 223902902 988169031 720895772 701813783 61355446 964138210 867634588 111021686 325278126 182704319 621925235 30414917 939481526 687927563 839582777 42871388 36198741 974673694 488922598 393345683 352960756 810394323 140687822 57258739 327956659 406593077 723113089 33804287 256932178 559340674 367029778 723662179 815867060 489847084 111594791 709360200 838114781 429256854 892994603 603263940 330825102 882474365 23040355 822257097 977689175 348283789 22236673 951019556 918359905 509868840 329584777 248187230 350282956 941941136 98867540 456947783 249829236 504483110 380110632 945530156 78175200 954869270 432531929 381392315 719743509 513685432 654739988 639049845 444354461 333833222 419189038 124700825 616401182 410759617 861571583 101338929 851140003 78998592 961861588 552527745 319426666 307870632 904448968 540426484 849400644 145721012 48906650 243932675 546225038 286074701 738213524 256753069 228733085 996447766 345239803 860177002 728816350 888027395 648827399 904271278 853098614 299323662 504104878 453916430 897287726 410750306 127251338 898932348 45663356 48391427 537790839 857876270 88559536 804359343 793754457 66001698 68264642 687063984 254893764 836367347 566924695 343640496 727909948 817185275 552655952 837842779 903612549 142354506 650196653 909620882 488202987 369397223 923858101 964134351 678491650 949421679 897178905 871012817 1432376 820739704 165207701 788674256 842154894 536203533 815437322 567569873 915639034 199259268 823476590 248380322 473423759 681295148 134186748 234098795 46383024 435058394 581539965 943849825 101702900 656099693 984477941 534382415 156984883 906285102 727244398 108499091 381173600 941971691 217938634 111628253 937700056 489903292 196284006 948009871 114265219 153555590 613042914 16308032 710093035 91612214 368449010 437400645 712112621 435063894 890396727 812422216 546004696 952862503 911812743 536899468 383523564 432227045 185085155 475671129 809250302 313694636 797089921 290055500 444461540 496477452 178629981 521588758 963791500 438362773 987172413 203565519 690185201 384776092 787930146 754242198 43458861 399429720 59723391 359952143 228148511 412246482 526184677 826867303 610178499 994349934 362703209 960752937 149446647 278463404 508031379 794171878 947199554 290612679 971203729 669317509 565407966 540717439 581876917 365164111 867084844 316261184 983037681 743782064 228582180 139235379 168356786 404396656 315458011 829427022 105258924 784714885 234373993 5945472 375778216 355539005 626482364 44799478 813968522 132896981 747829800 839375644 3120376 254969092 465318507 325921940 547489889 875125898 905748567 800044267 681585889 405127935 528796458 603299773 47062847 169474525 436077804 843407864 318483507 919235408 793825105 653742963 827126430 993975302 512181349 385657351 226237670 631546000 725620029 797920326 489807115 199493273 359382171 249851005 858998646 800046780 905613547 54145524 659984290 436620490 145332097 555142932 321057892 60600852 427964900 7454411 560364487 412919020 745930733 955063330 858593006 757128779 756416167 903055696 980243599 740439494 803333504 836514599 712293303 825925498 900799527 838474575 211135810 252427865 524832903 186462155 961631694 340850790 920810343 453051312 763191594 741165779 138190788 429777315 246871427 303785497 27760388 140907605 984840516 646802283 388120364 498006568 283852322 37905353 76649806 445653598 121932436 617572561 695630463 209797795 606618167 705645475 33234222 75891407 156549983 637293187 136766711 908350530 9737129 728990802 826486808 761673350 688210157 173529948 703295848 572163664 622711176 767867843 513827261 997488053 317322722 338906109 438792784 738926914 7718243 122708199 321769799 289718295 436370860 479836451 296633669 394471708 804879692 176098330 382869386 927412604 829367483 693761318 680296681 437070959 321263905 857348363 293490769 115626669 115095378 858281319 299018104 487716171 660577518 841064462 315119972 684423069 327908995 497482093 689001477 645239996 440716694 825179874 946068500 821673357 440802266 822949439 326285757 342793119 320936532 786773177 709578536 865578173 701056546 225399600 939754692 283084584 322999528 879171968 370445803 749727572 15374539 509324946 863101874 921753843 137769954 176708912 346716560 905216014 702028135 619913529 48465682 31756226 830574881 413055805 643737135 257864914 264352409 778012959 48161207 530408761 686011386 346315761 80099985 12181281 828260160 183465835 291750103 970432727 989620993 872236661 332106810 573534552 763027007 374663792 633602496 739176763 582434742 194758632 474152601 256394465 901432659 288349110 553510918 598056997 484988431 220157956 359341628 303518595 153758951 546151507 272002209 137853402 370615800 288256986 672692098 40099243 676585347 401464393 64247982
169
15057405 432556524 582718465 180231986 875823802 100202420 790122790 970674530 718018895 744924703 56123250 211469343 199805784 333373112 595460390 540393280 666682330 787528047 773437167 219651474 949795769 518315913 416088462 122046375 602042127 427499502 389979290 718741625 268944758 8974491 433030347 456716333 808306706 344249459 198333954 511820076 429803290 609553435 66989406 243108033 738099586 462435354 689381413 38044607 717498778 2715037 528437476 222813180 897635460 78319015 939368678 841051111 746918437 831786519 798276685 469802446 811486638 514760082 587518545 469750244 840264223 564660728 489306836 64411279 476614213 631016643 191186325 734506028 566753652 291628646 602914939 83637961 342971398 416111880 900109215 805216548 306652102 50771822 463793686 143160086 980530428 194125875 354485959 504621042 8562038 767431181 742243299 192387657 530687198 204146500 728608524 376745627 699155703 266623438 739797295 717454088 706109162 174673848 577705990 417540536 221682826 436073281 371265706 712808220 993495226 455290722 784037167 174389528 256967360 735794025 697131180 380721143 951301927 978044689 556577374 716077023 904599645 859481762 71709640 333581983 472983185 812683376 698110966 433439620 185477546 321392586 168494719 396276608 462491075 968886009 759813922 968118288 871757428 783907236 831994226 559196329 27286948 783910023 639229712 152121373 474172105 952295953 868571425 864110217 791945540 983225982 234683218 236202300 895740566 841272502 512201353 355335182 119816306 26355194 97103916 868902788 861228766 269840700 636324184 908157139 723233455 830838318 371767065 15717057 112950356 657513857 905988492 226419488 364372350
297
174147741 86134632 810596557 194625261 410809064 470961122 795586802 417542837 456348661 542981458 460840983 733329718 571841669 43707130 827592530 732716166 901993065 669449778 733797851 795032618 19429511 153495620 404282140 66829503 991620517 77724161 783682921 66199766 319494603 450860624 636149905 919522382 34533284 221179236 927563395 908236641 460120193 103934075 166200640 509372682 987755540 206034596 716289248 454126676 594099712 268952830 963554025 776375630 848941500 235747185 103414935 399866036 400219419 914549061 728589194 810298440 18611747 907924961 202009256 976315631 359268162 41445359 693961895 843569721 545492717 497314510 214725160 457698252 910867324 301556169 525282844 507332149 634210362 722532922 582334575 435244159 422535858 502132674 195728802 644440021 920046825 654214273 155707804 405221495 662374996 383145799 806384624 294838284 276900902 868017736 657061455 148598334 910275299 195952436 282186616 466634421 952757461 922459815 779002470 990089020 96312023 943678380 436233796 586843279 307534089 147735463 579918353 489722781 45485732 418837468 557079056 452466614 319441863 25030328 714124863 55215380 799612026 406789772 787127282 903170630 51745944 884952613 66034678 299029991 730008238 953193784 839453038 865838217 14641806 802699200 416975703 813118954 757174606 627884125 378546083 69193904 732840273 437474327 777222169 215183531 756585987 635059661 276336489 757702669 402063528 835401044 645055807 800239683 748265849 172034368 445606329 234206775 269466149 535864456 158624344 629819244 869848003 65409911 89050757 286354848 460406181 585952619 73609009 86753461 644694059 826089686 711048757 218746184 293220707 5609923 831357111 588859951 510566513 384340254 975486538 221242015 237187134 435649178 89889516 395093397 362158959 629584912 579172939 720574464 961078254 639992354 903627930 965030425 194338199 23826325 394394109 398623161 984087180 239853291 221452375 426441885 24388181 393055395 551721002 723053686 771869794 62836688 395719805 751091299 371663110 976742338 200101883 858640535 38921045 329656966 11576001 835914223 811199700 367987992 755658779 348498734 71253366 471328920 620681420 629887326 838052760 344494867 995816818 172619045 191569306 960287603 212722224 902137004 365176792 134006796 462557301 747008869 841818988 844328348 992618466 651312613 821516100 105157198 11185038 956330904 738648496 923029413 622218667 552219692 333492862 888752048 285506394 762211962 644986364 215286372 145093759 321284720 728658301 251195988 44179280 656196802 611243777 875221794 201908129 227042236 647953425 841427544 317593682 761331984 754813443 686008507 494192642 369991172 988635056 435289771 350902279 267472131 253504925 286727049 290877993 787743638 597857537 890347833 284842157 156196221 914362501 414019268 648336657 670623677 839397510 324409429 112143138 769495613 744174618 256534099 433349643 105537678 97402468 99659102 898912976 842860988 173918883
881
162041690 154214589 890497535 418102851 880134699 170847337 506337544 411845514 486284321 327278640 82103253 608310379 261402227 99885750 192392003 861537694 149965206 961111335 318724717 101030534 156540737 552243214 10408379 130647338 151279066 78503648 985979237 853191838 175728191 220289269 112940384 221120709 176322382 489047419 319905811 98848933 997007391 476644335 335805801 301664524 524479148 848411182 502300501 660288779 940146039 324114214 789447266 566398238 31914187 482008960 314598758 638078040 553272664 118528163 19314284 295544935 701410745 138261931 59273159 355999770 179491688 263009585 902778585 689222867 140905549 683189877 187608367 353144172 849850623 711041714 60440624 664309658 87566283 970593116 47437084 727089957 938271338 631136800 156059142 568737143 214116829 351957064 394392315 851926796 83843558 736794941 132495093 357543014 138867542 399104334 227795518 700171962 976743942 846917640 579855084 911461619 948215035 99991399 273474299 212133610 974708028 635671167 333714131 338399421 403438213 591180867 65054061 941233713 189253176 742309281 109545730 30941428 183393674 298222803 697016195 225234057 274066427 103958388 885428513 933265106 779047090 157957177 781152879 926654974 506386628 430045016 501257869 479682776 6907155 358834273 404067888 795189305 86301245 675276294 923422397 918908418 325414681 69795644 365697716 192433109 784954136 486261679 936291873 436667767 554102309 242568327 749889851 649255064 922023640 323890761 343606031 416621149 371304582 894623206 46512842 220893744 35666099 344018772 787620428 180907131 879185267 894317693 500882836 900325501 140330265 851520986 946845103 490523370 762957565 223596359 713525287 33540510 613123098 748442385 830351945 498221407 863575777 676515909 897813441 922533694 559302666 488492755 967178342 755570907 461766520 439087999 37522474 181999811 878178952 833765721 387930665 655486606 515343060 339672755 110845206 508166710 318974390 555563281 983894788 933575996 439068430 857901978 314779946 183949023 71085160 913164162 199554153 424869325 435145624 30860515 478514466 250521269 518447981 466811556 757718146 827774625 842974356 653834783 133400736 636858251 305466029 574897510 455221767 687154601 102751065 419259897 502678106 105476797 698269737 98529845 60049337 697910624 475823885 963639141 264264510 96184069 678723473 878384104 125105523 149976211 676483228 88763659 184602038 188377753 647169894 536649842 686120235 987416063 281857996 33086134 759400323 787681280 687943551 368975234 931520828 82087351 95200184 360719903 551562057 573777087 918916083 5874242 418811490 225910044 483310268 176629298 295655795 86014055 815568629 466065297 681312041 427951216 586995999 546776876 391860983 719308955 425033506 901037722 3320721 597970380 974798685 545017398 699254587 16153326 195751892 642543038 724187950 165678436 841144259 554368495 240277714 11440453 843973751 299271805 579811160 974679322 545293449 569527013 327151231 492034379 585943034 480799398 147450722 393544556 324562758 735603532 749671611 148026808 259731113 132375399 498756769 393641319 450255290 768713913 163442612 720978722 471483026 262449880 991789801 493141641 446834444 955996981 88882443 568656916 570659677 336280407 980967661 370784301 977500505 653513233 497637619 901724463 486137158 878629157 658892831 319129516 567739251 780078871 493516568 447349487 724751890 620218786 483474566 2625443 985076578 426352966 331360834 766304228 394829683 145088861 809030755 783052106 213248296 884983326 831623603 615900746 805033841 208712025 366157034 696572883 783839084 138081551 685987660 545779525 617784706 490927762 129984073 878141155 186738975 270719788 157107062 522795855 295023921 238248071 951005304 182987505 347794094 14907596 578783352 913176399 69688649 256944850 531428719 891859767 277385302 703097879 377713895 367245684 641776965 933550223 339287698 31333021 641710787 672833585 163500219 555455582 521648498 726658446 183840830 457751858 358992189 136831076 50876480 81593429 745669559 104538544 333442579 392195365 846752524 821675945 60216818 789625100 302889632 862578520 282698501 512023532 382661097 10178267 916930896 776878217 75880097 662065330 639650647 120293970 110333509 640303329 656441630 61786515 82321960 969736616 903423364 860839397 243176129 929869058 330261207 289769409 660330014 274709608 617648988 968068467 81375470 750089623 137587870 872241522 148159064 75118671 373110058 933219864 462894755 104812439 565919458 20552554 127602796 292537534 192122398 223942333 817924719 986866625 753914201 102900611 313357956 281906861 269539279 838474666 586976835 880392860 554131243 692755828 315574053 648434252 141380251 238613562 823209758 295329731 451249799 490513263 974007025 726158216 510357326 388838849 295541063 723046021 519909542 776443096 476986734 850837424 620726739 96077248 259112319 612533512 276008448 783098998 28930385 33512571 298482506 210682293 791277432 998601100 90705252 771734630 878657222 234135341 192417324 257727282 69543573 844299313 592702899 576006275 696655815 271621381 302435387 22628422 927524644 837153820 358532061 378537427 126804554 629791050 403607736 576900613 73395092 219836899 922143858 956987170 387928283 827150753 922727586 545021989 7058999 290047769 888848372 762542323 442118771 300995483 351948112 409421891 990723570 814015093 364284287 246282357 296414502 352420852 780936065 440664721 225359956 247500856 865677154 859217010 650831126 519445833 279326685 243463707 281320374 654718280 632047955 555586246 331293699 594127426 640169146 74479322 677833963 755478234 155739088 387287084 763118635 344994193 268883894 475744572 263328362 913370724 333020719 174323850 994271359 306769327 765559160 245423180 565763853 222005646 991376040 501431639 30230813 63949 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}
	for ; t > 0; t-- {
		var n int
		fmt.Fscan(in, &n)
		evens := make([]int64, 0)
		var maxOdd int64 = -1
		for i := 0; i < n; i++ {
			var x int64
			fmt.Fscan(in, &x)
			if x%2 == 1 {
				if x > maxOdd {
					maxOdd = x
				}
			} else {
				evens = append(evens, x)
			}
		}
		if maxOdd == -1 || len(evens) == 0 {
			fmt.Fprintln(out, 0)
			continue
		}
		sort.Slice(evens, func(i, j int) bool { return evens[i] < evens[j] })
		var ans int64 = 0
		m := maxOdd
		for _, x := range evens {
			if x > m {
				ans++
				m += x
			}
			ans++
			m += x
		}
		fmt.Fprintln(out, ans)
	}
}