Input: 1878
917659165 68895839 174728601 910357879 843738408 143858996 555909103 169979832 592009868 913857915 833360001 977496237 285403884 752131322 860237474 63020116 139303078 469150308 614670276 396462743 556745556 330554971 967549335 28046680 474214177 669235418 300716640 202653480 522229945 973529822 759236864 628816424 433371537 853833123 760349295 792354819 353574843 494800267 938871781 863185969 273977507 705565554 646685975 515329078 632178675 20330294 276192805 616571545 616085280 634662994 747751023 666385446 146817862 35890901 477330723 286857399 345737156 370659343 294801708 762136303 918703175 597978903 61565564 6569014 786970023 793342785 431390001 191845664 16010634 164516338 217607837 520128568 194399301 263894964 306812549 230480025 703082866 355123109 854471408 185152586 7491…
Output: 1 1 2 3 1 1 2 1 4 9 1 12 1 2 3 1 2 3 4 1 2 1 11 1 2 3 1 1 3 18 1 1 1 4 1 2 1 2 9 1 1 2 1 1 2 1 2 3 1 7 11 1 1 1 3 1 2 3 1 20 22 1 1 1 4 5 1 1 1 2 4 6 1 2 3 1 11 1 18 1 1 3 4 1 2 3 48 76 1 1 2 1 4 1 2 7 1 1 11 1 2 1 2 5 1 1 3 1 1 2 4 5 6 1 2 9 1 1 3 4 1 18 19 1 2 3 1 2 1 1 3 1 2 1 2 1 6 39 1 2 1 2 1 4 1 1 1 8 1 1 2 3 5 1 1 1 4 1 2 1 1 9 1 26 1 2 1 4 1 1 1 2 1 4 11 1 1 3 1 2 1 4 1 1 21 1 1 2 4 1 2 1 1 5 1 32 1 2 3 1 1 3 1 5 9 1 2 12 1 2 1 2 1 2 3 1 5 1 1 1 3 1 1 2 3 5 15 1 2 1 1 1 1 24 1 26 1 1 1 1 5 242 1 1 3 4 1 1 1 1 1 6 1 1 13 1 2 3 4 5 1 7 8 1 1 2 4 13 1 15 1 2 1 4 5 1 1 36 1 2 1 4 1 1 2 8 9 1 1 2 4 1 1 1 2 18 1 1 21 1 1 2 4 1 1 2 1 1 1 3 1 6 1 2 1 12 1 15 1 1 3 1 1 6 1 8 1 1 3 1 5 1 1 3 1 37 1 2 1 340 1 2 1 2 1 1 5 1 1 3 1 2 1 1 1 2 4 358 1 2 1 2 5 6 7 1 1 2 1 2 1 1 2 4 1 1 3 4 1 14 1 …