Input: 509
272621 942016 964080 940016 343325 606737 75022 106034 110356 450259 969493 383839 835952 335251 583339 455906 902877 95208 303183 680134 95108 189449 95606 907869 835867 68503 380147 458195 676900 336969 364926 651871 259378 635018 909457 4466 724196 761507 758419 973251 262248 662871 389764 252410 819143 535053 569353 943939 141408 395337 419018 474572 571590 242609 72998 961144 987928 437350 127404 829313 551052 967956 411795 531782 343386 807738 64227 372597 639820 315098 138663 416375 236667 301552 966035 394906 225526 156267 153490 374536 953984 257257 156745 553471 742633 332743 358548 527217 427910 883694 672898 943845 34837 591335 330088 186575 445620 227870 955891 774842 996374 402462 220582 814696 515386 723708 818257 43414 880623 167424 37221 459339 855345 58360 214992 314603 368993 300371 543793 361278 106317 544985 580165 134972 267295 291609 600932 403991 242241 659917 632548 471542 126437 733179 706816 251778 734886 961151 519071 772000 566623 794679 88443 919580 785993 763722 375657 318339 797421 237650 893944 990240 221049 364789 94552 354961 164594 789070 656318 41264 595167 217191 608055 708216 651307 244645 164184 422358 774565 941191 611555 952372 513340 923090 925885 474948 747770 787025 629276 361163 76207 253833 178500 280271 742343 401140 445528 429601 562999 543591 451583 830215 680407 300511 887518 146624 784523 417254 863158 977641 564372 121642 352167 247770 689748 204785 973390 872867 617997 67268 616822 216512 387173 139296 104856 616395 539441 966794 639092 307803 811373 824666 379593 989715 35105 535923 61030 196779 684440 202004 282496 323192 489476 468924 951011 861859 923169 871684 310069 3957 310375 781154 585219 860774 297269 803885 237662 400584 310161 50037 178121 388084 589140 364069 271175 48179 226942 588983 620710 958936 778203 398274 49361 134783 630074 101771 991472 104626 583842 462803 609056 93394 753952 354770 664815 807459 755084 914122 956723 698701 10420 953174 109963 662227 161033 173811 657650 450714 652719 708670 635427 475555 894931 5843 347939 125915 31751 76692 127683 175327 304336 626740 988430 547913 333092 912437 901834 587754 310581 434881 183052 307817 704638 107715 358712 520813 252137 452016 400106 19892 500826 890978 86311 681493 321607 473211 821041 396868 32964 181439 189867 218906 737085 205982 461968 735209 910803 692253 360118 472276 675847 580468 151088 561937 408806 82546 625288 978401 377004 286513 288432 409746 460210 169981 756712 943010 566777 526340 260299 732046 476355 233606 12723 351695 725010 231042 597343 807510 367593 961731 760538 509574 91932 129978 472773 939108 637304 986700 750010 643678 872083 150804 263767 507318 205348 227675 894082 291233 43410 100109 743068 46781 211537 105801 533905 635954 424877 527860 962733 60607 196323 172881 81184 164535 820567 851556 724926 328415 202848 826714 845355 758448 873118 703663 73826 953288 332985 707570 696549 20175 915793 289704 24592 764739 598743 954649 992380 44695 159835 811276 570777 924837 957445 320398 116591 32836 888949 131793 92497 536542 866296 219725 612605 619321 846451 549544 729594 14257 713363 929671 218433 528285 948683 115413 795257 893471 609656 41740 167312 695965 817764 997281 780993 531610 839024 352478 926764 807191 138906 491609 425877 806252 219654 427591 717114 78122 200829 914101 90117 6109 880281 603235 710969 809066 281716 72900 557885 771404 798862 584823 284241 81697 519471 296006 615728 30642 498064 859519 608715 356565 555378 689006 459097 70658 508740 898193 565191 107216 839746
Output: 4