Input: 267
56288814 258741551 258424135 487715240 616396476 605005428 411680882 473103678 386417040 261071302 641863857 144336320 466178432 304236495 951643358 285015876 832804394 16461683 572206019 329264820 489501043 949379384 145352528 836188927 524661615 677014175 666896202 277836283 269326458 15549217 267863492 661346089 348016813 93612657 501647526 436898998 78479482 757892374 47834503 544033178 305937978 956165043 625715718 460460859 828097065 268230835 167967634 99616432 477440440 542148463 782553984 184051153 369234067 282443955 283166905 360601448 603824039 391934050 678758829 364104689 236477987 562191249 276000333 710622912 290274027 256896336 178580960 256039965 164252219 988165636 807431444 827129097 416775671 267862144 965078291 466619661 237797369 63662340 61917629 525832072 12479940 210749790 504705916 189128043 334355668 180443274 807535421 456932975 160350175 224665873 362130702 262578907 795408088 159066915 510357534 124123581 201913435 503633708 40282795 721972241 567125806 169755469 283877791 789217483 526941949 69746188 759849896 250445535 83886361 769550834 967391968 200460787 668467198 869431448 691665243 667631905 308252580 449433426 13680730 31004693 72584719 387368619 226576939 210040787 699941841 691528592 561860498 52847405 459599015 247098208 776782899 622149843 683777011 678856833 586981109 702810542 795617373 635894924 203104362 482951168 679684470 529084214 97836358 73963480 682363443 411840199 91276116 945954204 295367235 516830671 686773732 656243884 536005224 142990150 10087293 881997164 341798579 363194890 4264875 320924401 148639183 2240467 195832974 910173307 108128810 505467594 533299300 410217514 619280240 502992324 661953902 664630486 970240124 531071326 980523801 197847234 600954112 548581335 68667983 57742543 610276494 632877305 610995344 397738963 367263328 791049003 805686992 70771217 316922849 107173918 182173125 551350693 535073286 915521149 783256596 847836688 130681452 425078130 524865089 59032125 140664935 671582272 44876545 50589487 173148272 642266512 236553261 347485465 545352330 191133362 371703139 111415704 93089465 440493824 811563375 55616473 932331044 4348293 41759160 239444725 877980252 779877839 351801724 996918093 278679395 943965934 30007554 56236917 783076303 616029627 468095877 789319407 308980867 889736563 927488574 171749541 778350374 472753848 362902633 666689351 808984466 398360321 437191932 927727379 281269959 393065702 908222406 270694504 558800188 321277296 87455955 524108413 289257526 176658018 359691050 824307492 388854917 898610355 651026474 514234686 918310174 673824964 462156691 179966618 139512242 691202094 765332141
Output: 9