Для кожного префікса заданого рядка S, який складається з N символів (кожен символ має ASCII-код від 97 до 126 включно), ми хочемо знати, чи є префвкс періодичним рядком. Тобто, для кожного i (2 ≤ i ≤ N), ми хочемо знайти таке найбільше K > 1 (якщо воно є), що префікс рядка S довжиною i, може бути записаний у вигляді A^K, тобто повторена K разів деяка частина рядка A. Звичайно ж, ми хочемо знати, який період K.
Вхідні дані складаються з декількох тестів. Кожен тест складається з двох рядків. Перший містить N (2 ≤ N ≤ 1000000) - розмір рядка S. Другий рядок містить сам рядок S. Вхідні дані завершуються рядком, який містить нуль.
Для кожного тесту вивести у окремому рядку "Test case #" і порядковий номер тесту, а потім, у окремих рядках для кожного префіксу довжини i, вивести його період, якщо K > 1. Виводити розмір префіксу i та його період K через один пропуск, розміри префіксів повинні йти у порядку зростання. Між різними тестами вивести порожній рядок.