Теперь когда вы предложили ложную запись на странице 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.
