eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

GATTACA

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Институт биоинформатики и медицины (IБM) в вашей стране занимается изучением ДНК некоторых организмов, включая человека. Прежде чем анализировать ДНК организма, исследователи должны извлечь ДНК из клеток организма и декодировать его с помощью процесса, называемого "секвенированием".

Метод, используемый для декодирования последовательности ДНК, называется "дробным секвенированием". Он применяется для декодирования длинных цепочек ДНК путем разрезания многих случайных копий одного и того же ДНК для создания более мелких фрагментов. Метод последовательно читает символы ДНК (A, C, G и T) с помощью специальной машины, после чего собирает их вместе, используя специальный алгоритм для построения всей последовательности.

Как правило, цепь ДНК имеет множество сегментов, которые повторяются два или более раз в последовательности (эти сегменты называются "повторениями"). Повторения не полностью определяются методом дробного секвенирования, так как повторный процесс монтирования не в состоянии различать два новых идентичных фрагмента подстрок из двух отдельных повторений.

Ученые института успешно декодировали ДНК многих бактерий из одной семьи другим методом секвенирования (более дорогим, чем дробное секвенирование), что позволило избежать проблемы повторений. Биологи посчитали это пустой тратой денег, так как по их мнению в изученных ДНК бактерий отсутствуют большие повторяющиеся фрагменты.

Биологи хотят, чтобы Вы написали программу, определяющую наибольшую подстроку, которая повторяется не менее двух раз в заданной последовательности ДНК.

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

В первой строке входного файла содержится целое число T с указанием количества тестов (1T100). Каждый тест состоит из одной строки S текста, являющейся последовательностью ДНК длины n (1n1000).

Каждая последовательность S содержит только буквы A, C, G и T.

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

Для каждой входной последовательности вывести в одной строке сначала наибольшую подстроку, повторяющуюся не менее двух раз в строке S, а потом через пробел количество ее повторений в S.

Если имеется две или более повторяющихся подстроки максимальной длины, то вывести лексикографически наименьшую из них.

Если в S повторений нет, то вывести сообщение "No repetitions found!"

Пример

Входные данные #1
6
GATTACA
GAGAGAG
GATTACAGATTACA
TGAC
TGTAC
TTGGAACC
Выходные данные #1
A 3
GAGAG 2
GATTACA 2
No repetitions found!
T 2
A 2
Источник 2013 Colombian Collegiate Programming League (CCPL), Contest 3, April 6, Problem B