На циклической ленте записаны маленькие латинские буквы. Для ролевой игры требуется вырезать хотя бы \textbf{k} одинаковых слов. При этом чем длиннее это слово будет, тем интереснее будет игра. Найдите длину наибольшего слова, которое можно вырезать хотя бы \textbf{k} раз. \InputFile Во входном файле задано множество тестовых данных. В каждой строке описан ровно один тест: число \textbf{k} и не пустая строка - буквы записанные на ленте. Ввод заканчивается концом файла. Суммарное количество букв на всех лентах в одном тесте не превосходит \textbf{10^5}. Все числа во входном файле целые, положительные, не превосходящие \textbf{10^5}. \OutputFile Для каждых входных данных выведите ответ на поставленную задачу - длину наибольшей строки.