Рассмотрим строку \textbf{S = s_1s_2s_3...s_\{n - 1\}s_n} над алфавитом \textbf{Σ}. \textit{Циклическим расширением} порядка \textbf{m} строки \textbf{S} назовем строку \textbf{s_1s_2s_3...s_\{n - 1\}s_ns_1s_2...} из \textbf{m} символов; это значит, что мы приписываем строку \textbf{S} саму к себе, пока не получим требуемую длину, и берем префикс длины \textbf{m}. \textit{Циклической строкой} \textbf{Š} назовем бесконечное циклическое расширение строки \textbf{S}. Рассмотрим суффиксы циклической строки \textbf{Š}. Очевидно, существует не более |\textbf{S}| различных суффиксов: (\textbf{n+1})-ый суффикс совпадает с первым, (\textbf{n+2})-ой совпадает со вторым, и так далее. Более того, различных суффиксов может быть даже меньше. Например, если \textbf{S = abab}, первые четыре суффикса циклической строки \textbf{Š} - это: \textbf{Š}_1 = \textbf{ababababab}...\textbf{Š}_2 = \textbf{bababababa}...\textbf{Š}_3 = \textbf{ababababab}...\textbf{Š}_4 = \textbf{bababababa}... Здесь существует всего два различных суффикса, в то время как |\textbf{S}| = \textbf{4}. Отсортируем первые |\textbf{S}| суффиксов \textbf{Š} лексикографически. Если два суффикса совпадают, первым поставим суффикс с меньшим индексом. Теперь нас интересует следующий вопрос: на каком месте в этом списке стоит сама строка \textbf{Š}? Например, рассмотрим строку \textbf{S = cabcab}: (1) \textbf{Š}_2 = \textbf{abcabcabca}...(2) \textbf{Š}_5 = \textbf{abcabcabca}...(3) \textbf{Š}_3 = \textbf{bcabcabcab}...(4) \textbf{Š}_6 = \textbf{bcabcabcab}...(5) \textbf{Š}_1 = \textbf{cabcabcabc}...(6) \textbf{Š}_4 = \textbf{cabcabcabc}... Здесь циклическая строка \textbf{Š} = \textbf{Š}_1 находится на пятом месте. Вам дана строка \textbf{S}. Ваша задача - найти позицию циклической строки \textbf{Š} в описанном порядке. \InputFile Единственная строка \textbf{S} (\textbf{1} ≤ |\textbf{S}| ≤ \textbf{30}), состоящая из прописных латинских букв. \OutputFile Выведите номер строки \textbf{Š} в описанном порядке среди первых |\textbf{S}| суффиксов.