Input: 217
607447 195720 6384 170459 346186 203515 262138 777936 913745 547194 634944 197659 591423 162321 798942 154911 486183 577542 547116 12578 144322 62323 835051 463892 48110 691812 912214 383407 555165 648068 899192 27977 264003 235335 508353 736132 74824 316816 839873 543133 264493 388570 147257 70017 26875 972557 569184 539124 245026 613491 918440 920062 745093 344243 969554 598248 143573 675622 809700 254743 737901 184583 956681 182123 941992 553010 956539 177979 60482 432415 340888 686959 319047 327306 286126 186569 205813 586864 216019 657434 369092 779749 179367 658993 158407 3931 809025 872980 353793 881063 857097 844825 588909 394709 561030 453388 848014 156028 666436 804781 718702 358900 154650 637185 56613 435794 196179 521970 958016 491479 5849 281889 351927 523480 603946 791991 654063 628519 343208 145039 91430 321807 890828 551368 953139 133450 605352 666141 369100 397958 654236 390842 41683 386254 970201 567421 376061 627627 473177 880420 713090 273884 691013 389649 381915 242893 296138 386773 947348 308024 691525 660800 463916 391177 626837 199975 449856 967132 833005 602898 409319 907118 770498 955730 291658 586409 238296 184803 985942 819086 449189 94091 699350 529158 247174 387861 432803 796011 432921 514128 322265 440179 308976 306218 200315 929163 206922 200340 133631 357539 398027 39285 606966 551704 506167 208111 506308 296032 281182 944630 848723 199364 618057 937788 551886 569209 518194 180778 674846 380250 632079 837436 802868 184509 869414 277828 507320
Output: 972557