Подстрока — это несколько подряд идущих символов в строке. Префикс строки — это подстрока, включающая первый символ строки. Суффикс строки — это подстрока, включающая последний символ строки.

Рассмотрим строку «квалификация». Строки «валик» или «акация» не являются её подстроками, т.к. буквы этих строк не идут в ней подряд. «валиф» и «каци» являются подстроками, при этом они обе не являются ни префиксом, ни суффиксом. «квал» является префиксом, а «кация» суффиксом строки. Сама строка «квалификация» является собственным суффиксом и префиксом.

В данной задаче мы считаем, что номера символов в строке индексируются с нуля.

Периодом строки S назовём минимальное положительное целое число T, для которого для любого 0 ≤ i < |S| верно, что S[i] = S[i mod T], где i mod T — остаток от деления i на T.

Грань строки — это её непустой префикс, который не является всей строкой и при этом равен её суффиксу. Сложностью строки назовём число различных периодов её граней. Динамической сложностью строки назовём сумму сложностей всех её префиксов.

Для заданной бинарной строки S и для каждого целого i от 1 до 25 требуется найти бинарные строки длины |S| + i, в которых строка S является префиксом, а их динамическая сложность будет наибольшей.

В единственной строке находится бинарная строка S, 0 ≤ |S| ≤ 10⁵, состоящая только из символов {X, .}.

Для каждого i от 1 до 25 требуется вывести максимальную динамическую сложность строки S + T, где |T| = i.