Повторювані підрядки#7530
Аналіз рядків часто зустрічається в застосунках з біології та хімії, таких як дослідження ДНК та білкових молекул. Одна з цікавих задач полягає у визначенні кількості підрядків, які повторюються принаймні двічі в довгому рядку.
Вам потрібно знайти кількість повторюваних підрядків у рядку, що містить не більше ніж символів. Потрібно враховувати будь-який унікальний підрядок, який зустрічається більше одного разу. Наприклад, у рядку "aabaab" є повторюваних підрядків: "a", "aa", "aab", "ab", "b". У рядку "aaaaa" повторюваними підрядками є "a", "aa", "aaa", "aaaa". Зазначимо, що повторювані підрядки можуть перекриватися (як "aaaa" у другому прикладі).
Перший рядок містить кількість тестів (не більше ). Кожен з наступних рядків не порожній і містить до символів.
Для кожного тесту виведіть в окремому рядку кількість різних унікальних повторюваних підрядків. Відповідь поміщається в знакове -бітове ціле.
Приклад 1