Input: 944
750772550 589474096 24051728 924727301 101208408 577745989 103980156 95845754 408425200 73539018 566447821 549720585 555384421 455917060 820026125 265517132 285674903 397673980 403129664 882610446 384041162 482228564 704714095 456977060 278522326 415373364 498102438 2123395 15210473 924396890 490984484 229473402 639540630 691704795 82515192 397679412 487448850 119531005 169820019 611711609 472125863 831579721 834639638 918685649 555482932 552238760 156206094 813180244 376126529 949853841 288429602 279829781 293866158 947084901 775818913 3759135 876683102 172025886 738417189 881391747 944912981 782269063 905441964 748398271 68306817 433501516 707022582 827143714 79621573 8842923 542329702 135357691 669458056 177156512 600151441 952206373 799643363 810007670 736509766 172397026 60453632 …
Output: 1 1 1 4 1 2 1 1 3 1 5 1 2 1 11 1 2 3 4 16 1 2 3 1 1 2 4 1 2 26 1 1 3 4 1 2 3 1 2 6 1 12 13 14 1 1 1 4 1 50 1 1 3 4 1 1 3 1 2 6 7 1 2 1 1 2 3 5 1 1 3 1 5 1 2 76 1 2 1 1 1 3 5 1 1 8 1 88 1 1 3 1 2 1 4 8 1 2 1 2 5 1 2 1 105 1 2 1 1 2 1 2 1 2 5 1 12 1 1 1 4 1 6 1 2 1 127 1 1 3 4 1 2 1 1 1 1 4 1 9 1 2 1 1 2 6 1 17 1 1 2 4 5 6 1 8 1 2 1 4 13 35 1 2 1 2 3 4 7 1 2 1 4 1 1 7 1 2 3 4 1 1 3 1 5 1 1 3 1 1 1 12 1 1 1 2 35 1 1 3 74 1 1 2 3 1 6 1 2 1 1 11 1 2 1 2 1 2 1 6 1 1 2 1 4 1 6 7 15 1 2 18 1 1 1 2 4 1 6 1 2 1 4 1 13 1 1 16 17 1 2 1 1 3 6 1 2 1 1 1 6 1 1 2 3 1 2 19 1 2 1 2 1 6 1 64 1 1 3 1 5 6 1 8 9 1 1 3 4 14 1 1 3 4 1 2 21 1 2 1 2 1 4 1 8 9 1 1 3 1 14 1 1 3 1 2 3 1 2 1 1 2 1 5 1 2 1 2 3 4 1 1 2 3 24 1 2 1 2 3 1 7 1 1 2 11 1 37 1 1 3 1 1 3 1 5 1 1 11 1 2 1 1 1 4 366 1 2 3 1 1 3 1 2 6 10 1 2 13 14 …