Najkrótszy okres [B]

Limit pamięci: 128 MB

Okresem słowa nazywamy takie słowo , które jest nie dłuższe niż i dla którego istnieje liczba naturalna , taka że jest prefiksem (tj. początkowym fragmentem) słowa . Okresami słowa taktakt są więc tak, taktak oraz taktakt.

Nauczycielka napisała na tablicy bardzo długie słowo. Jaś niezainteresowany lekcją wypisał w zeszycie wszystkie słowa powstałe przez usunięcie ze słowa na tablicy jednej literki. Teraz chciałby wybrać takie słowo z zeszytu, którego najkrótszy okres ma jak najmniejszą długość. Napisz program, który rozwiąże jego problem.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę przypadków testowych. Dalej następuje wierszy. Każdy z nich zawiera jedną liczbę całkowitą () oznaczającą długość słowa napisanego na tablicy, po czym następuje słowo składające się z małych liter alfabetu angielskiego.

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. -ty wiersz powinien zawierać odpowiedź na -te zapytanie: jedną liczbę całkowitą równą długości najkrótszego ze wszystkich najkrótszych okresów słów wypisanych w zeszycie Jasia.

Przykład

Dla danych wejściowych:

1
8 ababcaba

poprawną odpowiedzią jest:

2

Wyjaśnienie do przykładu: Dla słowa z powyższego przykładu Jaś zapisze w zeszycie słowa, których najkrótsze okresy mają następujące długości:

• babcaba - 5,
• aabcaba - 6,
• abbcaba - 6,
• abacaba - 4,
• abababa - 2,
• ababcba - 6,
• ababcaa - 6,
• ababcab - 5.

Autor zadania: Jacek Tomasiewicz.