eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Вырезание слова

Вырезание слова

Лимит времени 7 секунд
Лимит использования памяти 64 MiB

На циклической ленте записаны маленькие латинские буквы. Для ролевой игры требуется вырезать хотя бы k одинаковых слов. При этом чем длиннее это слово будет, тем интереснее будет игра. Найдите длину наибольшего слова, которое можно вырезать хотя бы k раз.

Входные данные

Во входном файле задано множество тестовых данных. В каждой строке описан ровно один тест: число k и не пустая строка - буквы записанные на ленте. Ввод заканчивается концом файла. Суммарное количество букв на всех лентах в одном тесте не превосходит 10^5. Все числа во входном файле целые, положительные, не превосходящие 10^5.

Выходные данные

Для каждых входных данных выведите ответ на поставленную задачу - длину наибольшей строки.

Пример

Входные данные #1
4 aaaa
1 aaaa
Выходные данные #1
1
4