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

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

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

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

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

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

Примеры