Input: 3051
618053176 314083038 835055546 102896244 49289808 84525554 455558095 95744879 167188315 360931981 706582482 693921611 108583588 232721645 292324490 735631690 328301892 565381687 367148783 719924300 946322596 716304016 455307545 926378999 808932377 160104819 830369592 565546578 659700631 52162968 430023990 216278230 206114134 806524215 290305501 97007592 654940121 25720538 954638499 278678976 633362702 6135386 280448562 702887843 760730406 815876237 11854996 895387059 818821649 657044887 1683810 621162351 433039685 691595693 846791402 874116523 582299391 243813022 89076123 878462576 533731445 769366696 347642231 633792615 194493711 938600728 628300980 821232845 444218472 959080492 208482323 476741843 633812506 277792955 904323395 404291281 551728264 81535335 423216953 314039959 26338779…
Output: 1 1 3 1 1 2 4 1 2 3 8 1 1 2 3 13 1 2 1 4 21 1 1 3 1 1 3 1 2 1 2 1 1 7 1 1 3 1 39 1 2 1 2 5 6 7 1 9 1 1 1 2 1 5 7 8 1 1 1 12 1 2 1 2 1 27 1 2 1 70 1 2 3 1 5 1 2 1 2 1 1 1 6 9 10 1 1 1 2 15 1 1 1 4 1 2 97 1 99 1 1 1 1 2 4 7 107 1 1 1 4 1 6 7 1 1 1 2 4 1 1 2 1 5 10 1 2 1 1 23 1 1 3 4 5 1 1 1 2 1 34 1 36 1 1 2 1 5 1 2 1 2 3 1 7 13 1 1 3 1 2 3 7 1 1 59 1 2 1 2 1 2 1 4 7 1 1 2 11 1 1 14 1 2 17 1 1 22 1 1 3 4 1 6 1 8 1 2 1 1 3 4 5 1 1 2 4 1 1 3 1 16 1 1 49 1 2 3 1 2 1 1 8 1 2 11 1 2 1 1 5 1 2 1 1 1 2 5 1 1 3 1 10 11 1 2 1 1 2 1 20 1 27 1 1 1 1 4 1 1 8 1 10 49 1 1 3 1 2 3 1 8 1 59 1 1 2 1 5 1 1 1 4 5 1 2 1 2 1 2 3 185 1 2 1 1 5 6 1 2 3 1 5 6 1 2 1 10 1 2 1 1 15 1 1 1 4 1 1 2 4 1 1 7 1 2 3 1 2 3 1 8 1 2 1 12 39 1 1 2 4 5 1 1 2 1 4 1 1 2 9 1 11 62 1 1 2 1 2 1 6 1 1 1 10 1 1 3 4 1 1 2 4 1 1 7 8 9 1 1…