Input: 1416
649207842 318408748 795523256 301978110 885887898 75959570 23534835 178245776 377141277 550416940 231565487 641102092 696420911 66379713 262313558 60777625 987217025 245663552 340514581 245605830 377800444 797101174 598183707 98331495 611851835 72213371 421802265 485295978 95638044 646352278 704545199 911901249 584778239 35698113 695128621 44408743 64497586 179213057 246675406 436379060 231846986 87363230 178404342 478616485 508616694 111606887 307087357 926135285 631442222 985752157 903557163 117269158 280013363 683043823 474647883 702905749 970198167 265470542 690830116 508085516 376441679 755800500 213947781 861448857 898429536 232698672 58445197 890995852 398423697 840381431 787172422 668718981 511307394 811831336 755669473 342781738 879712941 167281138 623032496 431083115 6445491…
Output: 1 1 3 1 5 1 1 3 4 5 1 7 8 1 2 1 17 1 2 1 4 5 1 1 3 1 2 3 1 8 9 15 1 1 3 1 2 3 4 5 1 1 2 9 10 1 2 31 1 33 1 1 2 3 1 5 7 1 2 1 1 5 1 7 8 1 1 3 1 2 1 1 1 4 1 1 9 1 2 1 4 1 1 3 28 1 2 3 1 2 1 1 5 9 1 1 3 1 42 1 2 1 2 5 6 1 8 1 10 1 12 1 1 2 1 1 6 1 2 3 1 1 1 7 1 2 1 2 3 4 1 2 7 1 2 3 13 1 2 1 2 1 2 1 1 3 8 24 1 1 3 1 1 3 1 1 107 1 1 2 4 5 1 7 1 9 1 2 3 1 14 1 1 17 1 19 1 1 1 2 24 1 2 1 2 3 1 7 1 1 1 11 1 2 1 2 1 6 1 2 20 1 1 3 1 2 3 1 52 1 2 162 1 1 3 1 2 3 1 8 1 10 1 2 1 1 1 1 5 1 2 1 2 12 1 1 2 1 2 3 7 1 2 244 1 1 1 3 5 1 1 8 9 1 1 3 1 2 3 1 1 3 7 1 2 13 1 15 1 2 3 1 2 6 22 1 2 1 1 2 4 1 2 3 4 5 12 13 1 2 3 1 5 19 1 2 3 54 1 2 1 2 1 6 1 1 3 4 5 1 1 1 15 70 1 1 2 1 4 1 2 1 1 10 11 1 2 3 1 5 1 1 3 1 1 1 12 1 95 1 1 1 1 1 1 7 1 1 2 1 1 3 6 1 1 1 4 5 6 1 1 3 1 5 12 1 1 3 30 1 1 2 3 1 2 37 1 1 2 …