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