Input: 2773
141103065 531590095 415996478 570088360 320812474 953596038 343394745 642662988 860778364 60775272 504802889 694641212 609010410 717131941 609112366 955189014 571018298 465185248 720226643 978039058 16809534 904735230 344732478 773622692 425330190 226753410 455579573 33884219 245311033 980780211 393545271 768064438 398561524 408447692 994200463 608647810 509771591 425021599 114240382 561142423 620013529 929505987 617867692 949920336 568669256 973927233 559335296 878019402 732794405 941838889 703171070 762932323 367041125 176477237 27779410 421400139 267055437 837721260 738049626 871789219 17672214 454257665 657459656 582081922 950157838 653176684 212231640 624878126 978407985 933143408 132126811 529588175 109626204 739874861 935984806 948564620 449498610 124305335 71516745 900795368 9…
Output: 1 2 1 4 1 6 1 2 3 1 2 3 1 5 1 16 1 1 3 20 1 2 1 2 1 1 3 1 2 30 1 2 1 2 35 1 1 1 1 4 6 7 1 9 1 11 1 2 1 4 1 2 1 1 1 4 1 8 1 10 1 2 3 1 19 1 1 2 34 1 1 2 1 4 6 7 1 1 1 4 5 1 1 2 3 5 1 7 1 1 1 4 1 59 1 2 3 1 1 2 4 5 1 1 1 1 1 2 1 16 1 1 3 1 21 1 2 3 1 2 6 1 2 1 1 1 3 1 129 1 2 3 1 2 6 7 1 2 1 1 1 2 4 8 1 1 2 3 4 1 1 1 1 2 4 1 2 1 15 1 2 1 1 1 3 7 1 1 2 4 5 28 1 2 1 4 1 6 1 36 1 1 2 4 1 1 1 1 53 1 2 1 2 1 4 1 2 1 1 2 4 1 12 1 2 1 4 1 1 2 1 5 1 1 3 27 1 1 1 3 1 6 1 1 1 2 38 1 2 1 4 1 2 3 1 1 2 4 1 2 1 2 1 6 1 1 13 1 2 1 1 5 6 1 1 3 1 1 3 1 1 3 1 5 6 1 40 1 2 1 1 3 4 1 1 7 1 1 1 4 14 1 56 1 2 1 1 3 1 2 1 1 8 1 2 69 1 2 1 1 1 6 1 8 1 117 1 1 1 1 5 1 7 1 1 3 1 5 1 2 3 1 5 6 1 2 3 22 1 2 1 4 5 1 2 3 1 5 1 2 1 9 1 2 39 1 2 1 2 1 2 1 1 3 6 9 1 2 1 1 1 2 7 1 2 60 1 1 2 1 5 6 1 2 1 2 1 1 13 1 1 76 1 1 …