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