Input: 342
507601667 799784273 131405458 270076547 820352364 99903710 3314253 739849164 797122114 347034756 205567638 175484173 127002443 862157479 960049594 674805108 404350181 646995841 901672470 26836571 973823274 606449593 656804643 770461425 613795467 291951863 849045731 442964678 230008549 34453062 279999977 659529988 807834507 517205959 778550786 497272745 372635813 786989180 99972021 292100139 507005110 392112463 939228379 652905801 472325416 569551435 231759026 965917165 752469477 946932402 129360224 628806668 122142194 17925074 342089635 972767076 428037974 970945983 821760382 816901949 609254840 458254272 525163271 780353545 885669965 103072163 721363872 474839875 486234770 787645815 190041272 606338968 350668481 799613629 574178792 771569010 80016810 547370700 212905358 418017406 297915229 837639652 327997591 634224167 314518356 256684948 789802741 755632224 149790480 861730399 14133996 589189062 423586972 353273672 910607218 186538536 733443447 420667845 206620682 707937217 450820643 566304303 192267330 287765565 694965472 992600838 776462080 334839176 12151747 572045406 211920830 955239437 380520116 391786246 329290211 5943534 989208332 90307365 714047928 760962401 236256008 926293580 310012991 134053939 794139612 819687725 23518159 243621586 894717647 261908077 132314877 622047522 288553914 477897914 397872961 494543602 711891880 39681788 682923467 96399541 415317508 268319439 836003370 557447166 352927736 16792424 156149353 737964793 860167035 751279713 833405628 229726885 762361744 753246118 43592200 104483507 924135605 643193718 732376102 719220065 170210016 508826511 18377524 339556556 118547745 439408082 383359239 631167564 624803140 101186745 884600063 359547847 965632783 676687330 682215439 558111519 156897629 902163362 391605336 831190306 770557126 89200618 68959729 932932968 776054463 315678929 -938472 136485308 727433859 290757600 793739679 354716336 478639970 325145568 717333332 963642105 339839519 196969594 238257203 532342018 524530480 89052121 114498534 284609018 380273816 821903010 97341043 916562343 994992110 31196535 637309919 990198777 417605314 520672187 499477196 526776552 378339064 575219758 618652631 69971213 783979919 536792242 482145488 65365746 593217304 32312157 987809288 875094477 636730914 503167199 850502943 665518539 775507524 207537251 871334227 664159852 238467982 36539756 544240849 397262188 116371721 789679242 645822083 503623200 264309074 549152176 428277785 147313320 889699276 625214188 280094265 864601863 308251932 996302321 209779925 612848199 208710757 47675145 766704228 422865744 261554742 942243993 479451909 652138390 131188555 51500845 856348783 193432580 662972511 730401626 70723114 159348659 302359614 870715179 47018526 920444884 9243994 942078811 916600144 252544252 433983702 185903157 443012553 309865895 972946142 265007100 115055592 482545206 142212529 326973348 721214244 366607872 729749014 47453234 508911252 871413879 113636092 879418682 434847101 287554405 648071650 571130515 3521894 939739438 938558828 860117434 97893667 654085481 807575772 849294051 687802314 149022284 702764443 808082002 885981444 854236796 572451049 966333629 875137303 741644876 293327677 184153997 68765985 789606236 241786728 529948694 487653105 523380396 377410856 430633287 857190843 294204358 550364758 538724303 663275908 866321140 568738680 630158623 772245689 714720858 491681634 188459472
Output: 172