Input: 858
663094108 584632981 65672565 944294723 902965320 264059522 653300685 527081493 394133160 2041221 953570600 928943405 802662858 95666556 540209269 590406317 429727500 145811593 784053773 696174553 859490419 365994268 737134346 182362587 743172044 704584455 385505706 653431000 60204831 46317306 271801173 22643317 287686807 857624901 57614406 285493003 861843766 273299375 95017771 836447123 333441623 522658933 129908229 523410322 805540019 191293453 499671199 192786238 473820583 549971657 924394675 832679868 542636074 136466791 484476704 347680459 68872141 578097640 833477885 274717447 68654391 879377762 632653497 861944244 826916535 182471844 952211435 917625596 540629173 659692222 552913191 889589971 685426758 627606273 177554373 516431562 569073528 787438843 164972539 743228594 4401240…
Output: 1 1 1 4 1 1 2 1 1 1 11 1 1 1 2 3 1 1 6 1 9 1 2 1 4 1 1 2 1 1 3 1 5 13 1 2 25 1 1 3 1 2 1 4 5 1 2 1 2 5 39 1 1 1 2 1 1 6 8 1 1 11 1 2 1 1 56 1 1 2 1 4 1 1 1 2 3 6 1 2 1 2 3 1 7 1 20 1 2 3 1 1 2 3 1 6 1 11 12 1 2 1 4 5 6 7 1 1 3 1 1 6 1 47 1 2 3 1 5 1 2 3 1 1 58 1 1 2 3 5 1 1 8 1 2 1 4 1 6 1 141 1 1 3 1 1 6 1 1 2 3 4 5 7 1 156 1 2 1 2 1 4 1 1 3 1 5 6 13 1 1 3 1 1 1 1 1 5 1 2 1 4 1 15 1 1 1 2 5 34 1 1 2 1 4 196 1 1 1 4 1 6 7 1 9 10 11 1 1 2 4 5 6 1 8 1 1 11 1 1 2 1 5 6 1 1 3 10 1 1 13 1 1 3 1 5 1 1 43 1 1 2 3 1 2 6 1 1 2 11 1 13 1 1 3 4 1 2 7 8 1 2 1 12 1 2 267 1 2 1 2 1 2 1 4 1 1 3 1 9 1 13 14 1 2 3 1 5 1 2 8 1 1 3 4 1 14 1 16 1 18 1 2 3 1 2 1 2 8 9 1 2 1 2 1 4 1 1 3 53 1 1 2 4 1 2 3 1 5 1 1 2 1 2 3 6 8 1 2 3 4 1 1 3 1 2 1 4 1 1 7 11 1 1 3 32 1 2 1 2 3 6 1 1 1 10 1 2 3 14 1 1 3 50 55 1 2 1 4…