GATTACA#1081
The Institute of Bioinformatics and Medicine (IBM) in your country studies the DNA of certain organisms, including humans. Before analyzing an organism's DNA, researchers must extract the DNA from the cells and decode it using a process called sequencing.
A technique used to decode a DNA sequence is called shotgun sequencing. This method is used to decode long DNA strands by cutting multiple random copies of the same DNA into smaller fragments. The method reads the DNA symbols (, , , and ) sequentially using a special machine, and then reconstructs the entire sequence with a special algorithm.
Usually, a DNA strand contains many segments that are repeated two or more times in the sequence (these are called repetitions). These repetitions cannot be completely determined using the shotgun sequencing method, as the assembly process cannot distinguish between two identical substrings from separate repetitions.
The institute's scientists successfully decoded the DNA of several bacteria from the same family using another, more expensive sequencing method that avoids the problem with repetitions. Biologists consider this a waste of funds, as they believe there are no large repeated fragments in the DNA of the studied bacteria.
Biologists would like you to write a program that, given a DNA sequence, finds the largest substring that is repeated two or more times in the sequence.
The first line contains an integer representing the number of test cases (1 \leq T \leq 100). Each test consists of a single line representing a DNA sequence of length (1 \leq n \leq 1000).
Each sequence contains only the letters , , , and .
For each input sequence, print a single line containing first the largest substring that is repeated at least twice in , followed by a space and the number of its occurrences in .
If there are two or more substrings of maximal length that are repeated, choose the lexicographically smallest.
If there are no repetitions in , print No repetitions found!
Example 1