Период
Для каждого префикса заданной строки 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 через один пробел, размеры префиксов должны идти в порядке возрастания. Между разными тестами вывести пустую строку.