D. Задача про строку "a"
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$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$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит строку $$$s$$$, состоящую из строчных латинских букв ($$$2 \leq |s| \leq 2 \cdot 10^5$$$).

Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество непустых строк $$$t \neq$$$ «$$$\texttt{a}$$$», удовлетворяющих всем ограничениям.

Пример
Входные данные
8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour
Выходные данные
4
4
1
16
1
2
3
1
Примечание

В первом наборе входных данных $$$t$$$ может быть «$$$\texttt{aa}$$$», «$$$\texttt{aaa}$$$», «$$$\texttt{aaaa}$$$» или всей строкой.

Во втором наборе входных данных $$$t$$$ может быть «$$$\texttt{b}$$$», «$$$\texttt{bab}$$$», «$$$\texttt{ba}$$$» или всей строкой.

В третьем наборе входных данных единственной подходящей $$$t$$$ является вся строка.