11512 - GATTACA

給定一組DNA序列，請找出重複次數大於等於二的最長子序列，並輸出其重複出現的次數。

Input

輸入資料的第一列有一個整數T表示測試資料的組數(1 <= T <= 100)，每組測試資料一列，表示一組DNA序列S，其長度為 n (1 <= n <= 1000)。你可以假定S僅包含字元A, C, G, T。

Output

請對每組測試資料輸出在S之中重複出現次數大於等於兩次的最長子序列，並輸出其出現的次數，並以一個空白字元隔開。若有不同組最長子序列存在，請輸出字典順序最小的該組子序列。若沒有重複的子序列則請輸出"No repetitions found!"。

Sample Input 

6
GATTACA
GAGAGAG
GATTACAGATTACA
TGAC
TGTAC
TTGGAACC

Sample Output 

A 3
GAGAG 2
GATTACA 2
No repetitions found!
T 2
A 2

---

原文出處