Если строку можно разбить на части вида $AABB$, где $A$ и $B$ — произвольные непустые строки, такое разбиение будем называть отличным.

Например, для строки aabaabaa, положив $A=\texttt{aab}$, $B=\texttt{a}$, мы получим один способ представить её в виде $AABB$.

У строки может не быть отличных разбиений, а может быть больше одного. Например, положив $A=\texttt{a}$, $B=\texttt{baa}$, мы тоже представим указанную строку в виде $AABB$. Однако у строки abaabaa отличных разбиений нет.

Дана строка $S$ длины $n$. Нужно найти общее число отличных разбиений среди всех способов разбиения всех её подстрок. Здесь подстрока — непрерывный фрагмент строки.

Обратите внимание:

1. Одинаковые подстроки, расположенные в разных местах, считаются разными, и отличные разбиения каждой из них включаются в ответ.
2. В одном разбиении допускается $A=B$. Например, у cccc есть разбиение $A=B=\texttt{c}$.
3. Сама строка тоже является своей подстрокой.

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

Входной файл — excellent.in.

Каждый входной файл содержит несколько наборов данных. В первой строке находится одно целое число $T$ — количество наборов. Гарантируется $1\le T\le10$.

В следующих $T$ строках находится по одной строке $S$, состоящей только из строчных английских букв и имеющей описанный в условии смысл.

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

Выходной файл — excellent.out.

Выведите $T$ строк, в каждой — одно целое число: общее число отличных разбиений среди всех разбиений всех подстрок строки $S$.

Примеры

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

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

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

3
5
4
7

Примечание

Обозначим через $S[i,j]$ подстроку строки $S$ от $i$-го до $j$-го символа включительно (нумерация начинается с $1$).

В первом наборе данных отличные разбиения есть у трёх подстрок:

• $S[1,4]=\texttt{aabb}$: отличное разбиение $A=\texttt{a}$, $B=\texttt{b}$.
• $S[3,6]=\texttt{bbbb}$: отличное разбиение $A=\texttt{b}$, $B=\texttt{b}$.
• $S[1,6]=\texttt{aabbbb}$: отличное разбиение $A=\texttt{a}$, $B=\texttt{bb}$.

У остальных подстрок отличных разбиений нет, поэтому ответ для первого набора данных равен $3$.

Во втором наборе данных отличные разбиения есть у четырёх подстрок, которые делятся на два вида:

У подстрок $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ одинаковое отличное разбиение: $A=\texttt{c}$, $B=\texttt{c}$. Однако они расположены в разных местах, поэтому нужно учесть его три раза.

У подстроки $S[1,6]=\texttt{cccccc}$ два отличных разбиения: $A=\texttt{c}$, $B=\texttt{cc}$ и $A=\texttt{cc}$, $B=\texttt{c}$. Это разные разбиения одной подстроки, и оба нужно включить в ответ.

Поэтому ответ для второго набора данных равен $3+2=5$.

В третьем наборе данных у каждой из подстрок $S[1,8]$ и $S[4,11]$ по два отличных разбиения. Подстрока $S[1,8]$ — пример из условия задачи, поэтому ответ равен $2+2=4$.

В четвёртом наборе данных у каждой из подстрок $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ по одному отличному разбиению, а у $S[3,14]$ — два. Поэтому ответ равен $5+2=7$.

Пример 2

См. файлы excellent/excellent2.in и excellent/excellent2.ans в каталоге участника.

Пример 3

См. файлы excellent/excellent3.in и excellent/excellent3.ans в каталоге участника.

Подзадачи

Во всех тестах гарантируется $1\le T\le10$. Все приведённые ниже ограничения относятся к одному набору входных данных, то есть каждый из $T$ наборов одного теста удовлетворяет этим ограничениям.

Пусть $n$ — длина строки $S$. Подробные ограничения для каждого теста приведены ниже: