Условие

---

L. ПОВТОРЕН НИЗ 
---
Даден е низ T с дължина N, съставен от големи латински букви. Напишете програма която да намира в него най-дългия подниз, които се среща поне два пъти. 
 
Вход: Първият ред на стандартния вход съдържа броя на тестовете, които програмата трябва да обработи. За всеки тест на един ред ще бъде зададен  низът T.  

Изход: За всеки тестов случай програмата трябва да изведе, на отделен ред на стандартния изход, най-дългия намерен подниз. Ако съществува повече отедин подниз, който се среща поне два пъти в T, програмата трябва да изведе най-малкия лексикографски такъв низ. 

Ограничения: 9 ≤ N ≤ 100000. 

Примерен вход: 
1 
ABAAAABAB

Примерен изход:
AAA