GATTACA |
A technique used to decode a DNA sequence is the ``shotgun sequencing''. This technique is a method applied to decode long DNA strands by cutting randomly many copies of the same strand to generate smaller fragments, which are sequenced reading the DNA bases (A, C, G and T) with a special machine, and re-assembled together using a special algorithm to build the entire sequence.
Normally, a DNA strand has many segments that repeat two or more times over the sequence (these segments are called ``repetitions''). The repetitions are not completely identified by the shotgun method because the re-assembling process is not able to differentiate two identical fragments that are substrings of two distinct repetitions.
The scientists of the institute decoded successfully the DNA sequences of numerous bacterias from the same family, with other method of sequencing (much more expensive than the shotgun process) that avoids the problem of repetitions. The biologists wonder if it was a waste of money the application of the other method because they believe there is not any large repeated fragment in the DNA of the bacterias of the family studied.
The biologists contacted you to write a program that, given a DNA strand, finds the largest substring that is repeated two or more times in the sequence.
The first line of the input contains an integer T
For each sequence in the input, print a single line specifying the largest substring of S
You can suppose that each sequence S
Output
If there are two or more substrings of maximal length that are repeated, you must choose the least according to the lexicographic order.
If there is no repetition in S
Sample Input
6
GATTACA
GAGAGAG
GATTACAGATTACA
TGAC
TGTAC
TTGGAACC
Sample Output
A 3
GAGAG 2
GATTACA 2
No repetitions found!
T 2
A 2
Colombia'2008