Якщо рядок можна розбити у вигляді $AABB$, де $A$ та $B$ — довільні непорожні рядки, таке розбиття називається відмінним.

Наприклад, для рядка aabaabaa, взявши $A=$ aab і $B=$ a, отримаємо один зі способів його розбиття у вигляді $AABB$.

Рядок може не мати жодного відмінного розбиття або мати їх декілька. Наприклад, взявши $A=$ a і $B=$ baa, також можна подати наведений рядок як $AABB$. Натомість рядок abaabaa не має відмінних розбиттів.

Задано рядок $S$ довжини $n$. Потрібно знайти загальну кількість відмінних розбиттів серед усіх способів розбиття всіх його підрядків. Підрядком тут називається суцільний фрагмент рядка.

Зверніть увагу:

1. Однакові підрядки на різних позиціях вважаються різними підрядками, і відмінні розбиття кожного з них враховуються у відповіді.
2. У розбитті дозволено $A=B$. Наприклад, для cccc існує розбиття $A=B=$ 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$).

У першому наборі даних відмінні розбиття мають загалом 3 підрядки:

$S[1,4]=$ aabb, відмінне розбиття: $A=$ a, $B=$ b;

$S[3,6]=$ bbbb, відмінне розбиття: $A=$ b, $B=$ b;

$S[1,6]=$ aabbbb, відмінне розбиття: $A=$ a, $B=$ bb.

Решта підрядків не мають відмінних розбиттів, тому відповідь для першого набору даних дорівнює $3$.

У другому наборі є дві категорії, загалом 4 підрядки з відмінними розбиттями:

Підрядки $S[1,4]=S[2,5]=S[3,6]=$ cccc мають однакове відмінне розбиття $A=$ c, $B=$ c, але через різні позиції його слід порахувати 3 рази.

Підрядок $S[1,6]=$ cccccc має 2 відмінні розбиття: $A=$ c, $B=$ cc та $A=$ cc, $B=$ c. Це різні розбиття одного підрядка, і обидва потрібно врахувати.

Отже, відповідь для другого набору даних дорівнює $3+2=5$.

У третьому наборі даних $S[1,8]$ та $S[4,11]$ мають по 2 відмінні розбиття. Підрядок $S[1,8]$ є прикладом з умови, тож відповідь дорівнює $2+2=4$.

У четвертому наборі даних $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ мають по 1 відмінному розбиттю, а $S[3,14]$ — 2. Отже, відповідь дорівнює $5+2=7$.

Приклад 2

Дивіться файли excellent/excellent2.in та excellent/excellent2.ans у каталозі учасника.

Приклад 3

Дивіться файли excellent/excellent3.in та excellent/excellent3.ans у каталозі учасника.

Підзадачі

Для всіх тестів гарантовано $1\le T\le10$. Наведені далі обмеження стосуються одного набору вхідних даних: усі $T$ наборів одного тесту задовольняють ці обмеження.

Нехай $n$ — довжина рядка $S$. Детальні обмеження кожного тесту наведено в таблиці: