Dövr
Hər bir verilmiş S ardıcıllığı üçün, hansı ki N simvoldan ibarətdir (hər bir simvolun ASCII-kodu 97 ilə 126 arasında daxil olmaqla), biz hər bir prefiksin periodik ardıcıllıq olub-olmadığını müəyyənləşdirmək istəyirik. Yəni, hər bir i üçün (2 ≤ i ≤ N), elə ən böyük K > 1 tapmaq istəyirik (əgər varsa), ki, i uzunluğunda olan S ardıcıllığının prefiksi A^K formasında yazıla bilsin, yəni A ardıcıllığının müəyyən bir hissəsi K dəfə təkrarlansın. Biz K periodunu bilmək istəyirik.
Giriş verilənləri
Giriş məlumatları bir neçə testdən ibarətdir. Hər bir test iki sətirdən ibarətdir. Birinci sətir N (2 ≤ N ≤ 1000000) - S ardıcıllığının uzunluğunu ehtiva edir. İkinci sətir isə S ardıcıllığının özünü ehtiva edir. Giriş məlumatları sıfır ehtiva edən bir sətirlə tamamlanır.
Çıxış verilənləri
Hər bir test üçün ayrıca sətirdə "Test case #" və testin sıra nömrəsini çıxarın, sonra isə hər bir i uzunluğunda prefiks üçün ayrıca sətirlərdə, əgər K > 1 olarsa, onun periodunu çıxarın. Prefiksin uzunluğunu i və onun periodunu K bir boşluq ilə ayıraraq çıxarın, prefikslərin uzunluqları artan sırada olmalıdır. Müxtəlif testlər arasında boş bir sətir çıxarın.