Вирізання слова

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

Вхідні дані

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

Вихідні дані

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

Приклади