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

Вам следует найти количество повторяемых подстрок в строке из не более чем 100 000 символов. Следует учитывать любую уникальную подстроку, которая встречается более одного раза. Например, строка "aabaab" содержит 5 повторяемых подстрок: "a", "aa", "aab", "ab", "b". В строке "aaaaa" повторяемыми подстроками являются "a", "aa", "aaa", "aaaa". Заметим, что повторяющиеся подстроки могут перекрываться (как "aaaa" во втором примере).

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

Первая строка содержит количество тестов (не более 10). Каждая из следующих строк не пустая и содержит до 100 000 символов.

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

Для каждого теста вывести в отдельной строке количество различных уникальных повторяемых подстрок. Ответ помещается в знаковое 32-битовое целое.