Інститут біоинформатики і медицини (IБM) у вашій країні займається вивенням ДНК деяких організмів, включаючи людину. Перед тим, як аналізувати ДНК організму, дослідники повинні отримати ДНК з клітин організму і декодувати його при допомозі процесу, який називається "секвенуванням". Метод, що використовується для декодування послідовності ДНК, називається "подрібненим секвенуванням". Він застосовується для декодування довгих ланцюжків ДНК шляхом розрізання багатьох випадкових копій однієї і тієї ж ДНК для створення більш дрібних фрагментів. Метод послідовно читає символи ДНК (A, C, G і T) при допомозі спеціальної машини, після чого збирає їх разом, використовуючи спеціальний алгоритм для побудови всієї послідовності. Як правило, ланцюжок ДНК має багато сегментів, які повторяються два або більше рази у послідовності (ці сегменти називаються "повтореннями"). Повторення не повністю визначаються методом подрібненого секвенування, так як повторний процес монтування не в змозі відрізняти два нових ідентичних фрагменти підрядків з двох окремих повторень. Вчені інституту успішно декодували ДНК багатьох бактерій з однієї сім'ї іншим методом секвенування (більш дорожчим, ніж подрібнене секвенування), що дозволило уникнути проблеми повторень. Біологи вважають це пустою витратою коштів, так як на їх думку у вивчених ДНК бактерій відсутні великі повторювані фрагменти. Біологи хочуть, щоб Ви написали програму, яка визначає найбйльший підрядок, який повторюється не менше двох разів у заданій послідовності ДНК. \InputFile У першому рядку вхідного файлу міститься ціле число \textbf{T} з вказуванням кількості тестів (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Кожен тест складається з одного рядкаи \textbf{S} тексту, який є послідовністю ДНК довжини \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}). Кожна послідовність \textbf{S} містить лише літери \textbf{A}, \textbf{C}, \textbf{G} і \textbf{T}. \OutputFile Для кожної вхідної послідовності вивести у одному рядку спочатку найбільший підрядок, який повторюється не менше двох разів у рядку \textbf{S}, а потім через пропуск кількість його повторень в \textbf{S}. Якщо є два чи більше повторюваних підрядків максимальної довжини, то вивести лексикографічно найменший з них. Якщо в \textbf{S} повторень немає, то вивести повідомлення "\textbf{No repetitions found!}"