Вам дана строка \(s\), состоящая из строчных латинских букв. Подсчитайте количество непустых строк \(t \neq\) «\(\texttt{a}\)», таких, что можно разбить\(^{\dagger}\) \(s\) на некоторые подстроки, удовлетворяющие следующим условиям:
- каждая подстрока равна либо \(t\), либо «\(\texttt{a}\)», и
- хотя бы одна подстрока равна \(t\).
\(^{\dagger}\) Разбиение строки \(s\) — это упорядоченная последовательность некоторых \(k\) строк \(t_1, t_2, \ldots, t_k\) (называемых подстроками), таких, что \(t_1 + t_2 + \ldots + t_k = s\), где \(+\) обозначает операцию конкатенации строк.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество непустых строк \(t \neq\) «\(\texttt{a}\)», удовлетворяющих всем ограничениям.
Примечание
В первом наборе входных данных \(t\) может быть «\(\texttt{aa}\)», «\(\texttt{aaa}\)», «\(\texttt{aaaa}\)» или всей строкой.
Во втором наборе входных данных \(t\) может быть «\(\texttt{b}\)», «\(\texttt{bab}\)», «\(\texttt{ba}\)» или всей строкой.
В третьем наборе входных данных единственной подходящей \(t\) является вся строка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour
|
4
4
1
16
1
2
3
1
|