GATTACA#1081
Інститут біоінформатики та медицини (IBM) у вашій країні вивчає ДНК деяких організмів, у тому числі й людини. Перед аналізом ДНК організму дослідники повинні вилучити ДНК з клітин і розшифрувати її за допомогою процесу, який називається секвенування.
Одна з технік, яка використовується для розшифрування послідовності ДНК, називається shotgun-секвенування. Цей метод використовується для розшифрування довгих ниток ДНК шляхом розрізання багатьох випадкових копій однієї й тієї ж ДНК на менші фрагменти. Метод зчитує символи ДНК (, , та ) послідовно за допомогою спеціальної машини, а потім відновлює всю послідовність за допомогою спеціального алгоритму.
Зазвичай у ланцюжку ДНК міститься багато сегментів, що повторюються два чи більше разів у послідовності (такі сегменти називаються повторами). Ці повтори не можуть бути повністю визначені методом shotgun-секвенування, оскільки процес збирання не може розрізнити два ідентичних підрядки зі шматків окремих повторів.
Вченим інституту вдалося розшифрувати ДНК кількох бактерій з однієї родини за допомогою іншого, дорожчого методу секвенування, який уникає проблеми повторів. Біологи вважають це марною тратою коштів, оскільки вони впевнені, що у ДНК досліджуваних бактерій немає великих повторних фрагментів.
Біологи хочуть, щоб ви написали програму, яка за даною послідовністю ДНК знаходить найбільший підрядок, що повторюється два або більше разів у послідовності.
У першому рядку міститься ціле число — кількість тестових випадків (1 \leq T \leq 100). Кожен тест містить один рядок , який є послідовністю ДНК довжини (1 \leq n \leq 1000).
Кожен рядок містить лише літери , , та .
Для кожної вхідної послідовності виведіть в одному рядку спочатку найбільший підрядок, який повторюється хоча б двічі у , потім пробіл та кількість його входжень у .
Якщо існує два або більше підрядків максимальної довжини, що повторюються, оберіть лексикографічно найменший.
Якщо у немає повторів, виведіть "No repetitions found!"
Приклад 1