I. Ложные Новости (сложная)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теперь когда вы предложили ложную запись на странице Facebook HC2, Хайди хочет оценить качество записи, прежде чем публиковать его. Недавно она столкнулась с (возможно, ложной) статьей о влиянии фрактальной структуры на мультимедийные сообщения, и теперь она пытается оценить подобное сообщение, которое определяется как

где сумма составляется из всех непустых строк p и , которое является количеством вхождений p в s в качестве подстроки. (Обратите внимание, что сумма бесконечна, но она имеет конечное число ненулевых слагаемых.)

Хайди отказывается делать что-либо ещё, пока она не придумает, как посчитать описанную сумму. Перед вами стоит задача помочь ей в этом. (Если вы хотите вместо этого убедить Хайди, что конечная строка не может быть фракталом в любом случае — не беспокойтесь, мы уже пробовали.)

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

В первое строке следует целое число T (1 ≤ T ≤ 10) — количество наборов тестовых данных.

Затем следуют описание T наборов тестовых данных. Каждое из них содержит одну строку s (1 ≤ |s| ≤ 100 000), состоящую из строчных букв латинского алфавита (a-z).

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

Выведите T строк (по одной для каждого набора тестовых данных). В каждой из строк выведите по одному целому числу — ответ на соответствующий набор данных.

Пример
Входные данные
4
aa
abcd
ccc
abcc
Выходные данные
5
10
14
12
Примечание

Строка s содержит другую строку p как подстроку, если p является непрерывной подпоследовательностью s. Например, ab является подстрокой строки cab, но не является подстрокой строки acb.