Обозначим через $a * b$ конкатенацию строк $a$ и $b$. Например, если $a = "abc"$ и $b = "def"$ то $a * b = "abcdef"$. Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом: $a^0$ = “” (пустая строка) $a^{n+1} = a * a^n$ По заданной строке $s$ необходимо найти наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$. \InputFile Каждый тест состоит из одной строки $s$, содержащей печатные (отображаемые) символы. Строка $s$ содержит не менее одного и не более $10^6$ символов. \OutputFile Для каждой входной строки $s$ вывести в отдельной строке наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$.