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